题解 P1174 【打砖块】

看到很多大佬写的都是些高端的dp。。。

小蒟蒻表示看不懂啊。。。

所以想了个简单的方法。。。

解释在代码最后。。。

#include<iostream>
using namespace std;
int n,m,k,a[201][201];
int sy[201][201],sn[201][201];
int fn[201][201],fy[201][201];
bool b[201][201];
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char ch;
            cin>>a[i][j]>>ch;
            if(ch=='Y') b[i][j]=1;
        }
    for(int i=1;i<=m;i++)
    {
        int cnt=0;
        for(int j=n;j>=1;j--)
        {
            if(b[j][i]==1)
                sy[i][cnt]+=a[j][i];
            else
            {
                cnt++;
                sy[i][cnt]=sy[i][cnt-1]+a[j][i];
                sn[i][cnt]=sy[i][cnt-1]+a[j][i];
            }
        }
    }
    for(int x=1;x<=m;x++) 第x列
        for(int y=0;y<=k;y++) 总共y颗子弹
            for(int z=0;z<=n && z<=y;z++) 要用z颗
            {
                fy[x][y]=max(fy[x][y],fy[x-1][y-z]+sy[x][z]);
                if(z!=0) fn[x][y]=max(fn[x][y],fy[x-1][y-z]+sn[x][z]); 后打x列
                if(y-z>0) fn[x][y]=max(fn[x][y],fn[x-1][y-z]+sy[x][z]); 先打x列
// 解释的好像有点问题。。。但大意就参照下文吧。。。
            }
    cout<<fn[m][k];
}
// 有借子弹的情况，预处理：sy[i][j],sn[i][j]表示第i列用j个子弹的得分
// y表示最后一颗不是在i列打的，n表示是
// fn[i][j],fy[i][j]表示前i列一共消耗j颗子弹，最后一颗是否打在第i列上
// 这个题很神奇。。。用到的方法就是先算出每列用的子弹数。。。会得多少分
// 然后dp的时候处理一下每种情况下最后一颗子弹就可以了
// 因为最后不一定要一棵树上吊死，可是子弹不够怎么办。。。
// 假装有。。。到底有没有就不知道了。。。如果没有预处理的没有用。。。
// 不会对后来的情况造成影响。。。 

而且跑的蛮快的。。。