luogu P1437 [HNOI2004]敲砖块

三角形向右对齐后
你想打掉一个砖块，那么你必须打掉右上方的三角形，前缀和维护
若是第i列若是k个，那么它右边的那一列至少选了k-1个
f[i][j][k] 表示从后向前选到第 i 列第j个一共打了k次的分数

// luogu-judger-enable-o2
#include
#include
#include
using std::max;
const int maxn = 57;
#define INF 0x7fffffff
inline int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); }while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x*f;
}
int n,m;
int g[maxn][maxn],s[maxn][maxn];
int f[maxn][maxn][2507];
int main()
{n=read();m=read();for(int i=1;i<=n;++i)for(int j=1;j<=n-i+1;++j)g[i][j]=read();for(int i=1;i<=n;++i)for(int j=1;j<=n-i+1;++j)s[i][j]=s[i][j-1]+g[j][i];for(int i=1;i<=n+1;++i)for(int j=0;j<=n+1;++j)for(int k=0;k<=m;++k)f[i][j][k]=-INF;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 l=max(0,j-1);l<=n-i;++l) {if(f[i+1][l][k-j]!=-INF)f[i][j][k]=max(f[i][j][k],f[i+1][l][k-j]+s[i][j]);}ans=max(ans,f[i][j][k]);}printf("%d\n",ans);return 0;
}

转载于:https://www.cnblogs.com/sssy/p/8455201.html

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