题目链接在这里：Problem - 7110 (hdu.edu.cn)
因为赛后是在洛谷上评测的，所以没有加多组数据
（赛后被告知这题洛谷上有原题的时候 内心一万匹草泥马奔过……）
我们需要考虑的只有两种情况，一种是打完k发子弹以后还剩了子弹，一种是打完k发子弹以后正好没子弹了。
这两种情况是有区别的，以同一列为例，如果当前k发子弹打完以后正好没了，那么后面如果跟着有Y砖头就不能再打了，如果还有子弹的话是还可以再打的。
状态转移方程的话也要分两种，一种是刚好打完，一种是打完以后还剩。
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=205; 4 int n,m,k,cnt; 5 int fa[MAX][MAX],fb[MAX][MAX],a[MAX][MAX],b[MAX][MAX],dd[MAX][MAX];// a无限 b刚好 6 bool c[MAX][MAX]; 7 char s[MAX][MAX]; 8 int main(){ 9 freopen ("k.in","r",stdin); 10 freopen ("k.out","w",stdout); 11 int i,j,zt,z; 12 scanf("%d%d%d",&n,&m,&k); 13 for (i=1;i<=n;i++) 14 for (j=1;j<=m;j++){ 15 scanf("%d %c",&dd[i][j],&s[i][j]); 16 if (s[i][j]=='Y') c[i][j]=true; 17 else c[i][j]=false; 18 } 19 // for (i=1;i<=n;i++) {for (j=1;j<=m;j++) cout<<dd[i][j]<<' ';cout<<endl;} 20 // for (i=1;i<=n;i++) {for (j=1;j<=m;j++) cout<<c[i][j]<<' ';cout<<endl;} 21 for (i=1;i<=m;i++){ 22 cnt=0; 23 for (j=n;j>=1;j--){ 24 if (c[j][i]) 25 a[i][cnt]+=dd[j][i]; 26 else{ 27 cnt++; 28 a[i][cnt]=a[i][cnt-1]+dd[j][i]; 29 b[i][cnt]=a[i][cnt]; 30 } 31 } 32 } 33 for (i=1;i<=m;i++) 34 for (j=0;j<=k;j++) 35 for (z=0;z<=min(j,n);z++){ 36 fa[i][j]=max(fa[i][j],fa[i-1][j-z]+a[i][z]); 37 if (z!=0) fb[i][j]=max(fb[i][j],fa[i-1][j-z]+b[i][z]); 38 if (j-z>0) fb[i][j]=max(fb[i][j],fb[i-1][j-z]+a[i][z]); 39 } 40 printf("%d",fb[m][k]); 41 return 0; 42 }