题目链接：点我点我:-) 题目描述： 在一个凹槽中放置了 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；
输出格式： 输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。
思路： 将三角形左对齐如下：
14 15 4 3 2333 33 76 22 13 1122 2331可以发现，每一列需要选的是从最上面开始连续的若干个，若是k个，那么它右边的那一列至少选了k-1个
感想： 这样水的题目不应该想不到，主要是被原图弄混乱了，原图会使DP有后效性，转移繁琐，转换一下就非常好做了，限制条件被巧妙地转换了。 对于DP题，在后效性或有奇怪的问题时，应该学会转换而消除原有干扰
代码：
//miaomiao 2017.2.8 #include<cstdio> #include<algorithm> using namespace std; #define For(i, a, b) for(int i = (a); i <= (int)(b); i++) #define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--) #define N (50+5) #define M (1500+5) int f[N][N][M], a[N][N], sum[N][N]; int main(){ int n, m, ans = 0; scanf("%d%d", &n, &m); For(i, 1, n) For(j, 1, n-i+1) scanf("%d", &a[i][j]); For(i, 1, n) For(j, 1, n-i+1) sum[i][j] = sum[i][j-1]+a[j][i]; f[n][1][1] = a[1][n]; Forr(i, n-1, 1) For(j, 0, n-i+1) For(k, 2*j-1, m){ if(k < 0) continue; For(x, max(j-1, 0), n) f[i][j][k] = max(f[i][j][k], f[i+1][x][k-j]); f[i][j][k] += sum[i][j]; if(i == 1) ans = max(ans, f[i][j][k]); } PRintf("%d/n", ans); return 0; }新闻热点
疑难解答
