P1174 打砖块
普通分组背包：50pts
题解说的啥？？？？（大雾）
看了半天
$s[0/1][i][j]$表示第$i$列用$j$发子弹，最后一发是1/否0打在该列上的价值
$f[0/1][i][j]$表示截止到第$i$列共用$j$发子弹，最后一发是1/否0打在该列上的最大价值
每次转移分成先打/后打第$i$列的情况
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cctype> 5 #define re register 6 using namespace std; 7 void read(int &x){ 8 char c=getchar(); x=0; bool f=1; 9 while(!isdigit(c)) f=(f&&c!='-'),c=getchar(); 10 while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); 11 x=f?x:-x; 12 } 13 int max(int &a,int &b){return a>b?a:b;} 14 int min(int &a,int &b){return a<b?a:b;} 15 #define N 202 16 int n,m,k,a[N][N],b[N][N],s[2][N][N],f[2][N][N]; 17 int main(){ 18 read(n); read(m); read(k); char pt[3]; 19 for(re int i=1;i<=n;++i) 20 for(re int j=1;j<=m;++j){ 21 read(a[i][j]); scanf("%s",pt); 22 b[i][j]=(pt[0]=='Y'); 23 } 24 for(re int i=1;i<=m;++i){ 25 int cnt=0; 26 for(re int j=n;j>=1;--j){ 27 if(b[j][i]) s[0][i][cnt]+=a[j][i];//不用多费子弹，且最后一发不可能打在‘Y’上 28 else ++cnt,s[0][i][cnt]=s[1][i][cnt]=s[0][i][cnt-1]+a[j][i]; 29 } 30 } 31 for(re int i=1;i<=m;++i) 32 for(re int j=0;j<=k;++j) 33 for(re int u=0;u<=min(j,n);++u){ 34 f[0][i][j]=max(f[0][i][j],f[0][i-1][j-u]+s[0][i][u]);//最后一颗子弹不打在前i列中 35 if(u) f[1][i][j]=max(f[1][i][j],f[0][i-1][j-u]+s[1][i][u]);//后打第i列 36 if(j>u) f[1][i][j]=max(f[1][i][j],f[1][i-1][j-u]+s[0][i][u]);//先打第i列 37 } 38 printf("%d",f[1][m][k]); 39 return 0; 40 }