题解 P3040 【[USACO12JAN]贝尔分享Bale Share】

functionendless · 2017-06-13 20:43:09 · 题解

简单到极致的DP题，大牛的大水题

f[i][j]->B_1=i,B_2=j,B_3=sum-i-j此方案可不可行

f[i][j]=f[i-v][j] | f[i][j-v];//如果有人问为什么不用f[i][j]的话继续往下看

其实本来每次更新sum是f数组要相应的完全更新

但是因为可以直接把这坨草丢到B_3上，所以就省去了memset的复杂度

代码如下（30行都没到）

#include<cstdio>
using namespace std;
bool f[1000][1000];
int n,sum;
inline int min(int a,int b) {return a<b?a:b;}
int main()
{
    int tmp,i,j,k;
    scanf("%d",&n);
    f[0][0]=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&tmp);
        for(j=min(999,sum);j>=0;j--)
            for(k=min(999,sum);k>=0;k--)
                if(f[j][k])
                {
                    if(j+tmp<999) f[j+tmp][k]=1;
                    if(k+tmp<999) f[j][k+tmp]=1;
                }
        sum+=tmp;
    }
    tmp=sum/3;
    for(i=tmp;i<=sum;i++)
        for(j=i;sum-i-j<=j;j--)
            if(f[i][j]) {printf("%d",i); return 0;}
    return 0;
}