求最大不能组合数


这个题其实还蛮有意思的,首先你要输入两个数,假如输入a和b,求以这两个为基数所不能组成最大不能组合数。举个栗子,假如a为4b为7,它们可以组成8(b为0个的情况),14(a为0个的情况),1115等等,但是它们所不能组合的最大数是17,超过17的任何一个数字都能被a和b相组合(不信你自己试试)。
样例输入
4 7
样例输出
17

分析

既然它们两个的组合数是以它们的倍数得来的,我首先想到的是两个for(0~n)循环来表示各自相乘的倍数,用arr[a*i+b*j] = 1来标记能组成的数字,但是很无奈,正确率只有75%,因为会涉及到数组越界且不好给定合适的大小。所以干脆放弃,后来知道了动态规划的思想后,这题就能过了,代码很简单,就不写什么注释了。

AC代码

//动态规划
#include <iostream>
const int N = 100000;  
using namespace std;
int x[100000], Max, a, b, i;    
int main(void)
{
    cin>>a>>b;
    x[0] = 1;               
    x[a] = 1;
    x[b] = 1;
    i = a>b?a:b;                                          
    while((i++)&&i<N)
    {
        if(x[i-a]==1 || x[i-b]==1)                    //动规思想,以两位数其中的一个呈递增关系的肯定是能组成的
        x[i] = 1;
        else Max = i;
    }
    cout<<Max;
    return 0;
}

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 求最大不能组合数


Truth is I missed those summer days