DP——Luogu1437 [HNOI2004]敲砖块

题面：Luogu1437
首先这个三角形不满足dp的无后效性
那么我们把这个三角形按左上角逆时针旋转90度一下
比如样例
2 2 3 4
8 2 7
2 3
49
转成
4
3 7
2 2 3
2 8 2 49
这样就可以DP了
定义状态：f[i][j][k]表示取了第i行第j列取了k块的最大值
因为取了第i行第j列以后第i行前面j个砖块全部会被取掉，所以维护一个前缀和s[i][j]表示第i行前j个的总值
那么状态转移方程就是：
f[i][j][k]=max(f[i-1][l][k-j])+s[i][j]（l从j-1到i-1枚举）
然后取max
还有那个j=0的时候需要搞一下，否则65分

#include
using namespace std;
int f[52][52][5001]={0},a[51][51];
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=n;j>=i;j--)scanf("%d",&a[j][i]);for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)a[i][j]+=a[i][j-1];for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)for(int k=j*(j+1)/2;k<=i*(i-1)/2+j;k++)for(int l=j-1;l<=i-1;l++)f[i][j][k]=max(f[i][j][k],f[i-1][l][k-j]+a[i][j]);int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)ans=max(ans,f[i][j][m]);printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！