【HNOI2004】 敲砖块 动态规划

题目描述：

在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖，从上到下每层依次减少一块砖。每块砖

都有一个分值，敲掉这块砖就能得到相应的分值，如下图所示。

14 15 4 3 23
33 33 76 2
2 13 11
22 23
31
如果你想敲掉第 i 层的第j 块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第

i-1 层的第j 和第j+1 块砖。

你现在可以敲掉最多 m 块砖，求得分最多能有多少。

输入输出格式

输入格式：
输入文件的第一行为两个正整数 n 和m；接下来n 行，描述这n 层砖块上的分值a[i][j],满足

0≤a[i][j]≤100。

对于 100%的数据，满足1≤n≤50，1≤m≤n*(n+1)/2；

输出格式：
输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。

输入输出样例

输入样例#1：
4 5
2 2 3 4
8 2 7
2 3
49
输出样例#1：
19

题解：
首先将砖块全部左对齐，变成一个直角三角形的模样。
可以得出如下结论：
1、每一列必须敲到由上到下的若干砖块。
2、如果某一列敲掉了k个砖块，那么其右边的那一列至少敲掉了k-1个砖块。
设 f[i][j][k] 表示从右到左已经敲到了第i列，其中第i列敲掉了j个砖块且总共敲掉了k个砖块的最大得分，那么转移方程为 f[i][j][k]=maxf[i+1][v][k−j]+a[1][i]+a[2][i]+……+a[j][i](v>=j−1) 。
最终答案为 maxf[i][j][k] 。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[56][56][506];
int a[56][56],ans=0;
int n,m;
int get()
{
 int x=0,p=1;
 char c;
 c=getchar();
 if (c==' ') return x*p;
 while (c<'0'||c>'9') {if (c=='-') p=-1;c=getchar();}
 while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
 return x*p;
}
int main()
{
 int i,j,k,v;
 n=get();m=get();
 for (i=1;i<=n;i++)
 for (j=1;j<=n-i+1;j++)
 {
 a[i][j]=get();
//          f[n-i+1][j].s=a[n-i+1][j];
//          f[n-i+1][j].s=a[n-i+1][j];
 }
 memset(f,-127,sizeof(f));
 f[n+1][0][0]=0;
 for (i=n;i>=1;i--)
 for (j=0;j<=n-i+1;j++)
 for (k=j;k<=m;k++)
 {
 for (v=j-1;v<=n-i;v++)
 if (f[i+1][v][k-j]!=-1&&k-j>=0)
 f[i][j][k]=max(f[i][j][k],f[i+1][v][k-j]);
//              f[i][j].w=f[i-1][j].w+f[i-1][j+1].w+1;
//              f[i][j][0][k]=max(f[i-1][j][0][k],f[i-1][j][0][k]);
//              printf("f[%d][%d]=%d    ",i,j,f[i][j].s);
//              printf("f[%d][%d]=%d\n",i,j,f[i][j].w);
//              printf("f[%d][%d][0][%d]=%d\n",i,j,k,f[i][j][0][k]);
 for (v=1;v<=j;v++)
 f[i][j][k]+=a[v][i];
 ans=max(ans,f[i][j][k]);
 }
 printf("%d",ans);
}