标签：DP
题目描述
在一个凹槽中放置了 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
设f[i][j][k]表示前i行打到第j列，共打了k次所能得到的最大分数
注意要从右向左处理，不然很容易WA
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
const int maxn=60;
int s[maxn][maxn],f[maxn][maxn][maxn*(maxn+1)/2],a[maxn][maxn];
int n,m,ans=0,x;int main()
{mem(s,0);mem(f,-1);scanf("%d%d",&n,&m);f[n+1][0][0]=0;rep(i,1,n)rep(j,1,n-i+1)scanf("%d",&a[i][j]);rep(j,1,n)rep(i,1,n-j+1)s[i][j]=s[i][j-1]+a[j][i];dep(i,n,1)rep(j,0,n-i+1)rep(k,j,m)rep(r,j?j-1:0,n-i)if(f[i+1][r][k-j]!=-1)f[i][j][k]=max(f[i][j][k],f[i+1][r][k-j]+s[i][j]);rep(i,1,n)rep(j,0,n-i+1)ans=max(ans,f[i][j][m]);/* rep(i,1,n){rep(j,0,i)printf("%d ",f[i][j][m]);printf("\n");}*/printf("%d\n",ans);return 0;
}