P1174 打砖块

· · 个人记录

题目在这里

思路

思路2分钟，调试9小时。
每列都可以分配随机个数的子弹，就是分组背包了，每列为一组，物品用前缀和表示。 就是如果有奖励子弹的话空间就不增加。 还要考虑如果这列最后打的是奖励子弹的砖块，那么其实需要到其他地方借一个，打完就能还，所以只要有一列最后是N的砖块这个方案即为满足。

设计f_{k,j,i}表示选到第k组，空间用了j个，是否选了结尾为N的物品。

剩下的亿点细节在代码中。

code

//这题最坑的在于空间可能为零，我们通常的直接二维背包写法会死得很惨！
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=410;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int ans,mp[N][N],n,m,x,bk[N][N],va[N][N],v[N][N],f[N][N][2];
signed main(){
    n=read(),m=read(),x=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mp[i][j]=read();
            char c;cin>>c;
            if(c=='Y')bk[i][j]=1;//第一维就是行，第二维就是列，开始时不同数组变来变去把自己搞懵了
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            va[i][j]=va[i+1][j]+mp[i][j];
            if(!bk[i][j])v[i][j]=v[i+1][j]+1;
            else v[i][j]=v[i+1][j];//对物品预处理
        }
    }
    for(int i=0;i<=m;i++)
        for(int j=0;j<=x;j++)
            for(int l=0;l<=1;l++)
                f[i][j][l]=-1e9;//给f数组设初值，用memset见祖宗
    for(int i=0;i<=m;i++)f[i][0][0]=0;//为啥我开始时写从1循环

    for(int k=1;k<=m;k++){
        for(int j=x;j>=0;j--)f[k][j][0]=max(f[k][j][0],f[k-1][j][0]),f[k][j][1]=max(f[k][j][0],f[k-1][j][1]);//继承上一组达到的最优解！
        for(int j=x;j>=0;j--){ 
            for(int i=n;i>=1;i--){
                if(v[i][k]>j)continue;
                if(!bk[i][k])f[k][j][1]=max(f[k][j][1],max(f[k-1][j-v[i][k]][0]+va[i][k],f[k-1][j-v[i][k]][1]+va[i][k]));
                else{
                    f[k][j][1]=max(f[k][j][1],f[k-1][j-v[i][k]][1]+va[i][k]);
                    f[k][j][0]=max(f[k][j][0],f[k-1][j-v[i][k]][0]+va[i][k]);
                    if(j>=v[i][k]+1)f[k][j][1]=max(f[k][j][1],max(f[k-1][j-v[i][k]-1][0]+va[i][k],f[k-1][j-v[i][k]-1][1]+va[i][k]));//你要是真的有子弹，多给一发不借也行啊
                }
            }
        }
    }
    for(int i=0;i<=x;i++)ans=max(ans,f[m][i][1]);//不一定子弹多就一定能打最优解，可能多余的用都用不了
    printf("%lld\n",ans);
    return 0;
}