->题目链接
题解：
一道dp好题。
#include<cstdio> #include<iostream> using namespace std; int a[210][210],s1[210][210],s2[210][210],dp1[210][210],dp2[210][210],n,m,k; bool vis[210][210]; int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ char ch[11]; scanf("%d%s",&a[i][j],ch); if(ch[0]=='Y') vis[i][j]=true; } for(int i=1;i<=m;i++){ int cnt=0; for(int j=n;j>=1;j--) if(vis[j][i]) s1[i][cnt]+=a[j][i]; else s1[i][++cnt]=s2[i][cnt]=s1[i][cnt-1]+a[j][i]; } for(int i=1;i<=m;i++) for(int j=0;j<=k;j++) for(int g=0;g<=n&&g<=j;g++){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-g]+s1[i][g]); if(g>0) dp2[i][j]=max(dp2[i][j],dp1[i-1][j-g]+s2[i][g]); if(j-g>0) dp2[i][j]=max(dp2[i][j],dp2[i-1][j-g]+s1[i][g]); } printf("%d ",dp2[m][k]); return 0; }
于2018.10.20：
莫名其妙，不知道为什么，原本AC的题目重新交上居然全WA了。
两个月前：
现在：
然后AC
#include<cstdio> #include<iostream> using namespace std; int a[210][210],s1[210][210],s2[210][210],dp1[210][210],dp2[210][210],n,m,k; bool vis[210][210]; int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ char ch[11]; scanf("%d%s",&a[i][j],ch); if(ch[0]=='Y') vis[i][j]=true; } for(int i=1;i<=m;i++){ int cnt=0; for(int j=n;j>=1;j--) if(vis[j][i]) s1[i][cnt]+=a[j][i]; else ++cnt,s1[i][cnt]=s2[i][cnt]=s1[i][cnt-1]+a[j][i]; } for(int i=1;i<=m;i++) for(int j=0;j<=k;j++) for(int g=0;g<=n&&g<=j;g++){ dp1[i][j]=max(dp1[i][j],dp1[i-1][j-g]+s1[i][g]); if(g>0) dp2[i][j]=max(dp2[i][j],dp1[i-1][j-g]+s2[i][g]); if(j-g>0) dp2[i][j]=max(dp2[i][j],dp2[i-1][j-g]+s1[i][g]); } printf("%d ",dp2[m][k]); return 0; }
一个人的夜，我的心应该放在哪里。