比赛 20101116 评测结果 AAAAWWWWWA
题目名称 打砖块 最终得分 50
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 08:52:20
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=220;
const int oo=1000000000;

int a[MAXN][MAXN],n,m,i,j,k,f[MAXN][MAXN],c[MAXN][MAXN],h,ans=0,s;
bool b[MAXN][MAXN];
char ch;

void init()
{
	freopen("gamea.in","r",stdin);
	freopen("gamea.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			scanf("%d%c%c",&c[i][j],&ch,&ch);
			if (ch=='N') b[i][j]=false;
			else b[i][j]=true;
		}
}

void solve()
{
	for (i=1;i<=m;i++)
	{
		h=1;
		j=n;
		a[i][0]=0;
		while (j>0)
		{
			if (b[j][i]) 
			{
				a[h-1][i]=a[h-1][i]+c[j][i];
				j--;
			}
			else
			{
				a[h][i]=a[h-1][i]+c[j][i];
				j--;
				h++;
			}
		}
	}
	f[0][0]=0;
	for (i=1;i<=m;i++)
		for (j=0;j<=s;j++)
			for (k=0;k<=j;k++)
			{
				f[i][j]=max(f[i-1][k]+a[j-k][i],f[i][j]);
				if (f[i][j]>ans) ans=f[i][j];
			}
	printf("%d\n",ans);
}

int main()
{
	init();
	solve();
	return 0;
}