自动搬运

查看原文

来自洛谷，原作者为

	functionendless **

搬运于2025-08-24 21:44:41，当前版本为作者最后更新于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;
}