UVALive 5790 Ball Stacking 解题报告

比赛总结

题目

题意：

有n层堆成金字塔状的球，若你要选一个球，你必须把它上面那两个球取了，当然也可以一个不取。求选的球最大的权值和。

题解：

将这堆球转成举行，第一行是(0,0)，第二个是(1,0)和(0,1)……如果选(i,j)的话,(i,j)到(0,0)之间的都要选。先把f(i,j)=(i,j)+……+(0,0)预处理出来。

然后用dp[j]表示在j这一列有球被选，且j+1～n-1没选过的最大权值。如果选了(i,k)且k>=j的话，f(i,j)就加了两次所以要减去。算出选(i,k)且k+1~n-1没选过的最大值后，更新dp[k]。

由于上述的方法要求所选点(i,k)必须之前没被选过，且选了它后，它所覆盖的矩形(0,0)~(i,j)之前必须都选了，所以i要从高到低，否则比如选了(i-1,j)也会更新dp[j],这时选(i,k)的话f(i,j)显然只有一部分被选两次。然后j要从左到右。

对于点(i,k)，要继承的dp[j]显然与k无关，所以可以记一个最优值。

//Time:135ms//Length:1122B#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <iostream>using namespace std;#define MAXN 1010#define INF 1000000007int sta[MAXN][MAXN];long long sum[MAXN][MAXN],dp[MAXN];int main(){    //freopen("/home/moor/Code/output","r",stdin);    int n;    while(scanf("%d",&n)&&n)    {        for(int i=0;i<n;++i)            for(int j=0,x=i,y=0;j<=i;++j,--x,++y)                scanf("%d",&sta[x][y]);        sum[0][0]=sta[0][0];        for(int i=1;i<n;++i)    sum[i][0]=sta[i][0]+sum[i-1][0],sum[0][i]=sta[0][i]+sum[0][i-1];        for(int i=1;i<n;++i)            for(int j=1;j<=n-i;++j)   sum[i][j]=sta[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];        for(int i=0;i<n;++i)    dp[i]=-(long long)INF*INF;        for(int i=n-1;i>=0;--i)        {            long long best=0;            for(int j=0;j<n-i;++j)            {                dp[j]=max(dp[j],best+sum[i][j]);                best=max(best,dp[j]-sum[i][j]);            }        }        long long ans=0;        for(int i=0;i<n;++i)    ans=max(ans,dp[i]);        cout<<ans<<'\n';    }    return 0;}