背包两联发...

这道题看上去和前一题相似,也是组合后求最值.依然可以开三位数组flag[i][f][j]表示该状态能否到达.然后跑20*2000*2000*2000.这样复杂度看来搞不了.考虑如何优化.

这道题和上一题不一样的地方在于:每个宝藏必须分给某个人.也就是说,对于第k个宝藏必须要求i+f+j==宝藏总大小才可以到达.这样我们可以减少一维了.

flag[f][j]表示第一个人f个第二个人j个的状态能否达到.刚开始当然flag[0][0]可以达到.然后对于每个宝藏t,如果flag[f][j]==1,那么flag[f+t][j]=flag[f][j+t]=flag[f][j]都能等于1.这三个式子分别表示t给第一二三个人的状态转移.

最后对于所有flag[f][j]=1的情况都可以拿来更新状态:ans=min(ans,max(f,max(j,sum-f-j)).

复杂度20*2000*2000不用优化.

int i,f,j,t,sum,ans;int flag[2010][2010],n;int main(){    flag[0][0]=1;    n=read();    for(i=1;i<=n;i++)    {        t=read();        for(f=sum;f>=0;--f)            for(j=sum;j>=0;--j)                if(flag[f][j])                    flag[f+t][j]=flag[f][j+t]=1;        sum+=t;    }    ans=sum;    for(f=0;f<=sum;++f)        for(j=0;j<=sum;++j)            if(flag[f][j])                ans=min(ans,max(f,max(j,sum-f-j)));    cout<