最大组合数

点击量: 76 次

这个题其实还蛮有意思的,首先你要输入两个数,假如输入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;
}
 【深度搜索】割绳子
【双向宽度搜索】九宫重排 
上一篇:【深度搜索】割绳子
下一篇:【双向宽度搜索】九宫重排


点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出


pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2019 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信
QQ
0:00