随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.1.2 Score Inflation (完全背包)
标准的完全背包问题。练练手吧。

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

#include <fstream>

using namespace std;

int f[10005], mark[10005], cost[10005];
int N,V;

int main(){
    int i,j;

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

    fin>>V>>N;

    for(i=1; i<=N; ++i)
        fin>>mark[i]>>cost[i];

    for(i=1; i<=N; ++i)
        //complete pack
        for(j=cost[i]; j<=V; ++j)
            if(f[j]<f[j-cost[i]]+mark[i])
                f[j] = f[j-cost[i]]+mark[i];

    fout<<f[V]<<endl;
    return 0;
}
posted on 2010-12-14 20:41 小阮 阅读(200) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


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