题意：

有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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         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
         
          =0;--i) { long long best=0; for(int j=0;j