问题标题: 酷町堂：1210 西瓜分配

Question

0

已解决

汪宇航

新手启示者

谁帮我攻克一下啊啊啊啊！！！！，凡是给核心/思路的人瓜分100豆！！！！！！！！！！！！

酷町豆刷题求解 C++ 2条评论 3 年，1 月前

Answer 1

已采纳

张皓轩

中级光能

核心（因为用DEV打的，所以是这样）：
for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) {
        V += v[i];
        c[i] = v[i];
    }
    hfV = V/2;
    for(int i=1; i<=n; i++) 
        for(int j=hfV; j>=v[i]; j--)
            f[j] = max(f[j], f[j-v[i]] + c[i]);
    if(V % 2 == 0) cout << (hfV - f[hfV]) * 2 << endl;
    else cout << V - 2 * f[hfV] << endl;
定义：
int n, V, hfV;
int v[50001], c[50001];
int f[50001];

Answer 2

李显晨

中级启示者

全局：
long long c[10000005],v[10000005],f[10000005],sum,v,n;
主函数：
输入n;
循环(1~n){
    输入c[i];
    v+=c[i];
    sum+=c[i];
}
v/=2;
循环(1~n){
    循环(int j=v;j>=c[i];j--) f[j]=max(f[j],f[j-c[i]]+c[i]);
}
cout<<sum-f[v]*2;

Answer 3

汪恺恒

中级启示者

01背包变形

问题标题: 酷町堂：1210 西瓜分配

3 个回答: