比赛 20101116 评测结果 AAAAWWWWWA
题目名称 打砖块 最终得分 50
用户昵称 lc 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 11:07:18
显示代码纯文本
#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 Sval[maxm][maxn],Spo[maxm][maxn];
int F[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]);
		}
	}
	for (int i=1; i<=M; i++)
		for (int j=N; j>=1; j--) Spo[i][j] = Spo[i][j+1] + Point[j][i];
	for (int i=1; i<=M; i++)
		for (int j=N; j>=1; j--) Sval[i][j] = Sval[i][j+1] + Val[j][i];
}

void work()
{
	F[0][0] = 0;
	for (int i=1; i<=M; i++)
		for (int j=0; j<=K; j++)
			for (int p=0; p<=N; p++)
			{
				int t = j - p + Spo[i][N-p+1];
				if (t<0) continue;
				if (F[i-1][t] + Sval[i][N-p+1] >F[i][j])
					F[i][j] = F[i-1][t] + Sval[i][N-p+1];
			}

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

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