P1174 打砖块

P1174 打砖块

普通分组背包：50pts

题解说的啥？？？？（大雾）

看了半天

$s[0/1][i][j]$表示第$i$列用$j$发子弹，最后一发是1/否0打在该列上的价值

$f[0/1][i][j]$表示截止到第$i$列共用$j$发子弹，最后一发是1/否0打在该列上的最大价值

每次转移分成先打/后打第$i$列的情况

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cctype>

 #define re register

 using namespace std;

 void read(int &x){

     char c=getchar(); x=; bool f=;

     while(!isdigit(c)) f=(f&&c!='-'),c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     x=f?x:-x;

 }

 int max(int &a,int &b){return a>b?a:b;}

 int min(int &a,int &b){return a<b?a:b;}

 #define N 202

 int n,m,k,a[N][N],b[N][N],s[][N][N],f[][N][N];

 int main(){

     read(n); read(m); read(k); char pt[];

     for(re int i=;i<=n;++i)

         for(re int j=;j<=m;++j){

             read(a[i][j]); scanf("%s",pt);

             b[i][j]=(pt[]=='Y');

         }

     for(re int i=;i<=m;++i){

         int cnt=;

         for(re int j=n;j>=;--j){

             if(b[j][i]) s[][i][cnt]+=a[j][i];//不用多费子弹，且最后一发不可能打在‘Y’上

             else ++cnt,s[][i][cnt]=s[][i][cnt]=s[][i][cnt-]+a[j][i];

         }

     }

     for(re int i=;i<=m;++i)

         for(re int j=;j<=k;++j)

             for(re int u=;u<=min(j,n);++u){

                 f[][i][j]=max(f[][i][j],f[][i-][j-u]+s[][i][u]);//最后一颗子弹不打在前i列中

                 if(u) f[][i][j]=max(f[][i][j],f[][i-][j-u]+s[][i][u]);//后打第i列

                 if(j>u) f[][i][j]=max(f[][i][j],f[][i-][j-u]+s[][i][u]);//先打第i列

             }

     printf("%d",f[][m][k]);

     return ;

 }