洛谷P1437 敲砖块
题目大意：给定n*n的上半个矩阵，每一点表示一个砖块。有敲掉该块砖能得到的相应的分值。对于(i,j)的砖块，若i==1，则可以直接敲掉；若i>1，则必须先敲掉(i-1,j)和(i-1,j+1);现在最多可以敲掉m块砖，求最大得分
sum[i][j]:第j列的前缀和
dp[i][j][k]:敲(j, i)的砖块，敲了k次的最大分数
敲掉i+1列的砖和1~i列的砖毛有关系，没有后效性，可以dp
状态转移：考虑状态(j,i)的砖，上一步状态有{(j-1,i+1),(j,i+1),…,(n-i,i+1)}，则在其中去一个最大值即可。
状态转移方程：dp[i][j][k]=max(dp[i+1][p][k-j]+sum[j][i]);(j-1<=p<=n-i)
#include 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！