#26. 打气球——Yucai OJ第18次测试

问题描述

ML很喜欢一个打气球的游戏,游戏规则如下: 初始状态，有n行m列的气球，ML有k发子弹。ML每次可以使用一发子弹，打爆某一列最下面的一个气球，并得到相应的分数。如图所示：

某一些气球被打爆以后，ML可以得到一发子弹的奖励。当ML使用完所有子弹或者所有的气球被打爆，游戏结束。 已知每一个气球被打爆的得分以及被打爆以后是否会奖励ML子弹，求游戏结束时，ML的最大得分。

输入格式

第1行包含3个整数 n m k。 接下来n行每行包含m个由正整数a和字符b组成的二元组，第i行第j个二元组表示第i行第j列的气球得分为a，如果b等于’Y’表示打爆该气球会奖励子弹，等于’N’表示不会奖励子弹。

输出格式

输出一个整数，表示ML的最大得分。

样例输入

3 4 2
9 N 5 N 1 N 8 N
5 N 5 Y 5 N 5 N
6 N 2 N 4 N 3 N

样例输出

13

数据规模和约定

对于20%的数据，满足1<=n,m<=5，1<=k<=10，所有的字符c都为N；

对于50%的数据，满足1<=n,m<=200，1<=k<=200，所有的字符c都为N；

对于100%的数据，满足1<=n,m<=200，1<=k<=200，字符c可能为Y；

对于100%的数据，所有的f值都满足1<=f<=10000。

题解

dp+公式+暴力。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=201;
int n,m,k,a[MAXN][MAXN];
int sy[MAXN][MAXN],sn[MAXN][MAXN];
int fy[MAXN][MAXN],fn[MAXN][MAXN];
bool b[MAXN][MAXN];
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>a[i][j]>>c;
            if(c=='Y'){
                b[i][j]=1;
            }else{
                b[i][j]=0;
            }
        }
    }
    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++){
        for(int y=0;y<=k;y++){
            for(int z=0;z<=n && z<=y;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]);
                }
                if(y-z>0){
                    fn[x][y]=max(fn[x][y],fn[x-1][y-z]+sy[x][z]);
                }
            }
        }
    }
    cout<<fn[m][k]<<endl;
    return 0;
}