[HNOI2004]打砖块（敲砖块）
题目：codevs1257、洛谷P1437
题目大意：有一些砖块呈倒三角形状，每块砖敲掉后有一个分数。除第一行外，敲掉一块砖必须先把上面两块砖敲掉。现在你能敲m块砖，求能得到的最大分数。
解题思路：此题是一道非常恶心的dp。我们先把砖块“左对齐”，然后敲掉砖块（i，j）（i>1）时，就必须先敲掉（i-1，j）和（i-1，j+1）。
设$f[i][j][k]$表示打到第i列第j块砖，一共打了k块砖时所得的分数，则有$f[i][j][k]=max(f[i][j][k],f[i+1][p][k-j](j-1\le p
时间复杂度$O(n^3m)$，然而常数很小。
注意行和列千万别搞混了。
还有codevs和洛谷的m的范围是不一样的，codevs里是$1\le m \le 500$，洛谷大概是$1\le m \le 1275$。我的f开到52*52*1300，稳过。
C++ Code：
#include
#include
#include
using namespace std;
int a[52][52],sum[52][52],f[52][52][1300];
int n,m;
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){for(int j=1;j<=n-i+1;++j){scanf("%d",&a[i][j]);}}for(int j=1;j<=n;++j){for(int i=1;i<=n-j+1;++i)sum[i][j]=sum[i][j-1]+a[j][i];}memset(f,-1,sizeof f);f[n+1][0][0]=0;int ans=0;for(int i=n;i;--i){for(int j=0;j<=n-i+1;++j)for(int k=j;k<=m;++k)for(int p=(j)?j-1:0;p
转载于:https://www.cnblogs.com/Mrsrz/p/7257290.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！