记录编号	22102	评测结果	AAAAAAAAAA
题目名称	打砖块	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	C++	运行时间	1.654 s
提交时间	2010-11-16 22:20:01	内存使用	1.27 MiB

#include<iostream>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 210,maxm = 210,INF = 1000000000;
int N,M,K;
int Val[maxn][maxm],Point[maxn][maxm];
int Sy[maxm][maxn],Sn[maxm][maxn];
int Fy[maxm][maxn],Fn[maxm][maxn];


void prep()
{
	scanf("%d%d%d\n",&N,&M,&K);
	for (int i=1; i<=N; i++)
	{
		for (int j=1; j<=M; j++)
		{
			char ch;
			scanf("%d %c",&Val[i][j],&ch);
			Point[i][j] = (ch=='Y');
			//printf("%d %d ",Val[i][j],Point[i][j]);
		}
		scanf("\n");
	}
}

void solve(int i,int p)
{
	int val = 0,tp = p;
	for (int y=N; y>=1; y--)
	{
		if (tp==0) break;
		val += Val[y][i];
		tp = tp - 1 + Point[y][i];
	}
	Sn[i][p] = val;
	
	val = 0; tp = p;
	for (int y=N; y>=1; y--)
	{
		tp = tp - 1 + Point[y][i];
		if (tp<0) break;
		val += Val[y][i];
	}
	Sy[i][p] = val;
}

void work()
{
	for (int i=1; i<=M; i++)
		for (int p=0; p<=N; p++)
			solve(i,p);
	
	for (int i=1; i<=M; i++)
		for (int j=0; j<=K; j++)
		{
			for (int t=0; t<=j; t++)
			{
				if (j<K)
				Fn[i][j] = max(Fn[i][j],Fn[i-1][t] + Sy[i][j-t]);
			}
			for (int t=0; t<=j; t++)
			{
				if (j-t) Fy[i][j] = max(Fy[i][j],Fn[i-1][t] + Sn[i][j-t]);
				if (t) Fy[i][j] = max(Fy[i][j],Fy[i-1][t] + Sy[i][j-t]);
			}
		}

	printf("%d\n",Fy[M][K]);
}

int main()
{
	freopen("gamea.in","r",stdin);
	freopen("gamea.out","w",stdout);
	prep();
	work();
	return 0;
}