随笔-141  评论-9  文章-3  trackbacks-0
USACO 4.1.1 Beef McNuggets (数论, gcd, 完全背包)

可以证明结果不会超过最大的两个数的最小公倍数（如果有的话, 这部分还没做)。

判断无限解可以按上面的方法，另外也可以算所有的数的最大公约数。

如果不是1，也就是说这些数不互质，那么一定没办法构成所有的不被这个最大公约数整除的数。当且仅当这种情况会有无限解。

/*
ID: lorelei3
TASK: nuggets
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAX = 70000;

bool f[MAX];
int n;
int a[15];

int gcd(int a, int b){
    if(b==0)
        return a;
    else 
        return gcd(b, a%b);
}

int main(){
    int i,j,k;

    ifstream fin("nuggets.in");
    ofstream fout("nuggets.out");

    fin>>n;

    for(i=1; i<=n; ++i)
        fin>>a[i];

    k=a[1];
    for(i=2; i<=n; ++i)
        k = gcd(k, a[i]);

    if(k!=1){
        fout<<0<<endl;
        return 0;
    }

    f[0]=true;

    for(i=1; i<=n; ++i)
        for(j=a[i]; j<=65536; ++j)
                f[j] = f[j]||f[j-a[i]];


    for(i=65536; i>=1; --i)
        if(!f[i])
            break;
    
    fout<<i<<endl;
    
    return 0;
}
posted on 2011-01-20 20:34 小阮 阅读(256) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮