小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：
在刚开始的时候，有nnn行×m \times m×m列的砖块，小红有kkk发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。(如图所示)
某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。
小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？
第一行有333个正整数，n,m,kn,m,kn,m,k。表示开始的时候，有nnn行×m \times m×m 列的砖块，小红有kkk发子弹。
接下来有nnn行，每行的格式如下：
f1c1f2c2f3c3……fmcmf_1 c_1 f_2 c_2 f_3 c_3 …… f_m c_mf1?c1?f2?c2?f3?c3?……fm?cm?
其中fif_ifi?为正整数，表示这一行的第iii列的砖，在打碎以后的得分。cic_ici?为一个字符，只有两种可能，YYY或者NNN。YYY表示有一发奖励的子弹，NNN表示没有。
所有的数与字符之间用一个空格隔开，行末没有多余的空格。
仅一个正整数，表示最大的得分。
3 4 2 9 N 5 N 1 N 8 N 5 N 5 Y 5 N 5 N 6 N 2 N 4 N 3 N
13
对于20%20\%20%的数据，满足1≤n,m≤5,1≤k≤101 \le n,m \le 5,1 \le k \le 101≤n,m≤5,1≤k≤10，所有的字符ccc都为NNN
对于50%50\%50%的数据，满足1≤n,m≤200,1≤k≤2001 \le n,m \le 200,1 \le k \le 2001≤n,m≤200,1≤k≤200，所有的字符ccc都为NNN
对于100%100\%100%的数据，满足1≤n,m≤200,1≤k≤2001 \le n,m \le 200,1 \le k \le 2001≤n,m≤200,1≤k≤200，字符ccc可能为YYY
对于100%100\%100%的数据，所有的fff值满足1≤f≤100001 \le f \le 100001≤f≤10000
看题解不是很懂，就按照自己的理解写写。
首先有一个前缀和，si[i][j],sr[i][j], si[i][j]表示在第i列，拥有j颗子弹并借子弹时能得到的分数,是一个理想的状态。sr[i][j]表示在第i列，
用j颗子弹能得到的分数，是一个实际的状态。
然后是dp方程。fi[i][j],fr[i][j].fi[i][j]表示前i列，用了j颗子弹，并借了子弹时能达到的最大分数，是一个理想的状态。fr[i][j]表示在前i列，
用j颗子弹能得到的实际的最大分数，也就是没有借子弹。所以我们最后的答案是fr[m][k].
上代码。
#include<bits/stdc++.h> #define maxn 201 using namespace std; int fi[maxn][maxn]; int fr[maxn][maxn]; bool vis[maxn][maxn]; int si[maxn][maxn]; int sr[maxn][maxn]; int a[maxn][maxn]; int n,m,k; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int w; char c[3]; scanf("%d%s",&w,c); a[i][j]=w; if(c[0]==‘Y‘) vis[i][j]=1; } } for(int i=1;i<=m;i++) { int cnt=0; for(int j=n;j>=1;j--) { if(vis[j][i]) si[i][cnt]+=a[j][i]; else { cnt++; si[i][cnt]=si[i][cnt-1]+a[j][i]; sr[i][cnt]=si[i][cnt-1]+a[j][i]; } } } for(int i=1;i<=m;i++) { for(int j=0;j<=k;j++) { for(int p=0;p<=j&&p<=n;p++) { fi[i][j]=max(fi[i][j],fi[i-1][j-p]+si[i][p]); if(p) fr[i][j]=max(fr[i][j],fi[i-1][j-p]+sr[i][p]); //当p大于0时，也就意味着可以先借给前i-1列一颗子弹 //使它从理想上的最大值变成实际的最大值，而实际上 //打完前i-1列之后是不消耗我们第i列的p颗子弹的，所 //以仍然会剩有p颗子弹打第i列，而剩余的p颗子弹只能 //达到第i列的一个实际最大值 if(j-p>0) fr[i][j]=max(fr[i][j],fr[i-1][j-p]+si[i][p]); //当j-p大于零时，也就意味着前i-1列可以先借给第i列一颗 //子弹，使它从理想上的最大值变成实际的最大值，而实际上， //当我们先打完第i列之后也没有消耗前面i-1列的j-p颗子弹 //（打到的是Y，所以边消耗子弹边得到子弹）剩下的j-p颗子弹 //也就只能得到前i-1列的实际最大值 } } } printf("%d",fr[m][k]); return 0; }
原文：https://www.cnblogs.com/lee454207074/p/11613962.html