2825 - 打砖块

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 128 MB

小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：
在刚开始的时候，有n行*m列的砖块，小红有k发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。
如图所示：

<img src="http://tk.hustoj.com:80/attached/image/20140706/20140706172147_72600.jpg" alt="" />

&nbsp;某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。<br />

小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？

题目输入

第一行有3个正整数，n，m，k。表示开始的时候，有n行*m列的砖块，小红有k发子弹。
接下来有n行，每行的格式如下：
f1 c1 f2 c2 f3 c3 …… fm cm
其中fi为正整数，表示这一行的第i列的砖，在打碎以后的得分。ci为一个字符，只有两种可能，Y或者N。Y表示有一发奖励的子弹，N表示没有。

&nbsp; &nbsp; &nbsp; &nbsp; 所有的数与字符之间用一个空格隔开，行末没有多余的空格。

对于20%的数据，满足1&lt;=n,m&lt;=5，1&lt;=k&lt;=10，所有的字符c都为N<br />

对于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

<div>
	<br />
</div>

题目输出

仅一个正整数，表示最大的得分。

输入/输出样例

输入格式

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

输出格式

C++解答

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=201;

int a[MAXN][MAXN];
int by[MAXN][MAXN],bn[MAXN][MAXN];
int sy[MAXN][MAXN],sn[MAXN][MAXN];
char c[MAXN][MAXN];
/*sn[j][i]：第j列打i发子弹，最后一个子弹打第j列的砖块。
  sy[j][i]：第j列打i发子弹，最后一个子弹不打第j列的砖块。
  bn[j][i]：前j列打i发子弹，最后一个子弹打第j列的砖块  。
  by[j][i]：前j列打i发子弹，最后一个子弹不打第j列的砖块.*/
  
int main()
{
	//freopen("game.in","r",stdin);
	//freopen("gamea.out","w",stdout);
	
	int N,M,K;
	scanf("%d%d%d",&N,&M,&K);
	
	for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            scanf("%d %c",&a[i][j],&c[i][j]);
        }
    }
    
    for (int i=1;i<=M;++i)//循环处理第几列 
    {
        int t=N;//t为行数 
        while (t>0 && c[t][i]=='Y')
		//如果第一个砖块是Y，那么相当于不用耗费子弹即可向上打 
        {
            sy[i][0]+=a[t][i];
            t--;//打掉这一层的砖块即可向上打 
        }
        
        //把刚开始Y砖块打完后，则下面没有砖块，从最后为Y的砖块的上一层开始 
        for (int j=1;j<=N && t>0;++j)
        {
            sn[i][j]=sy[i][j-1]+a[t][i];//第i列 
            sy[i][j]=sn[i][j];
            t--;
            
            while (t>0 && c[t][i]=='Y')
            //如果砖块是Y，那么相当于不用耗费子弹即可向上打
			{
                sy[i][j]+=a[t][i];
                t--;
                //打掉这一层的砖块即可向上打
            }
        }
    }
    
    /*for(int i=1;i<=M;++i)
    {
    	for(int k=0;k<=K;++k)
    	{
    		printf("%3d",sy[i][k]);
    	}
    	printf("\n");
    }
    printf("sy————————\n");
    
    for(int i=1;i<=M;++i)
    {
    	for(int k=0;k<=K;++k)
    	{
    		printf("%3d",sn[i][k]);
    	}
    	printf("\n");
    }
    printf("sn————————\n");*/
    
    /*for(int i=1;i<=M;++i)
    {
    	for(int k=1;k<=K;++k)
    	{
    		s[i][k]=s[i][k-1]+a[N-k+1][i];
		}
	}*/
	
    for(int j=1;j<=M;++j)
    {
    	for(int i=0;i<=K;++i)
    	{
    		for(int k=0;k<=N;++k)
			{
				if (k<=i)
                {
                    int tmp=by[j-1][i-k]+sy[j][k];
                    if (tmp>by[j][i]) by[j][i]=tmp;
                    
                    if (k<i)
                    {
                        tmp=bn[j-1][i-k]+sy[j][k];
                        if (tmp>bn[j][i]) bn[j][i]=tmp;
                    }
                    
                    if (k>0)
                    {
                        tmp=by[j-1][i-k]+sn[j][k];
                        if (tmp>bn[j][i]) bn[j][i]=tmp;
                    }
                }
			} 
		}
	}
	
	/*for(int i=1;i<=M;++i)
    {
    	for(int k=0;k<=K;++k)
    	{
    		printf("%3d",by[i][k]);
    	}
    	printf("\n");
    }
    printf("by————————\n");
    
    for(int i=1;i<=M;++i)
    {
    	for(int k=0;k<=K;++k)
    	{
    		printf("%3d",bn[i][k]);
    	}
    	printf("\n");
    }
    printf("bn————————\n");*/
    
	printf("%d",bn[M][K]);

	return 0;
}

上一题下一题代码讨论统计