洛谷P1437 [HNOI2004]敲砖块【巧妙dp】

        ——弃子

省选前做水dp
其实挺巧妙的

[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

#include
#include
#include
using namespace std;
inline int read(){char ch=getchar();int sum=0;while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9')sum*=10,sum+=ch-'0',ch=getchar();return sum;
}
#if 0
Writers: G.S.M. && Goes
#endif
int map[55][55],n;
int sum[55][55],m,ans;
int dp[55][55][3010];
#define num(x) (1+x)*x/2 
/*
dp[i][j][k]  打到第i列第j块一共打了k次的最大分数 
从右往左dp
这样做可以保证转移的时候
敲掉第i层第j块时 是从i-1层j+1块转移过来的
*/ 
int main()
{memset(dp,-20,sizeof(dp));n=read(),m=read();dp[n+1][0][0]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n-i+1;j++)map[i][j]=read();for(int j=n;j>=1;j--)for(int i=0,sum=0;i<=n-j+1;i++,sum+=map[i][j])for(int k=i;k<=m;k++)for(int l=max(0,i-1);l<=n-j;l++)dp[j][i][k]=max(dp[j+1][l][k-i]+sum,dp[j][i][k]);for(int i=1;i<=n;i++)for(int j=1;j<=n-i+1;j++)ans=max(ans,dp[i][j][m]);printf("%d",ans);   return 0;
}

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