记录编号	23009	评测结果	AAAAAAWWWA
题目名称	打砖块	最终得分	70
用户昵称	Pom	是否通过	未通过
代码语言	C++	运行时间	0.772 s
提交时间	2011-02-23 13:43:54	内存使用	1.23 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=202;

int n,m,p,i,j,k,l,ans=0;
int f[MAXN][MAXN][3],chartA[MAXN][MAXN],chartB[MAXN][MAXN],sc[MAXN][MAXN];
bool b[MAXN][MAXN];
char ch;

int main()
{
	freopen("gamea.in","r",stdin);
	freopen("gamea.out","w",stdout);
	scanf("%d%d%d",&m,&n,&p);
	for (i=m;i>=1;i--)
		for (j=1;j<=n;j++)
		{
			scanf("%d %c",&sc[j][i],&ch);
			if (ch=='N') b[j][i]=false;
			else b[j][i]=true;
		}
	memset(chartA,0,sizeof(chartA));
	memset(chartB,0,sizeof(chartB));
	memset(f,0,sizeof(f));
	for (i=1;i<=n;i++)
	{
		k=0;
		for (j=1;j<=m;j++)
		{
			if (b[i][j]) chartA[i][k]+=sc[i][j];
			else chartA[i][++k]+=sc[i][j]+chartA[i][k-1];
		}
		k=0;
		for (j=1;j<=m;j++)
		{
			if (!b[i][j])
			{
				chartB[i][++k]+=sc[i][j]+chartB[i][k-1];
				for (l=j-1;b[i][l];l--)
					chartB[i][k]+=sc[i][l];
			}
		}
	}
	for (i=0;i<=p;i++)
		f[0][i][2]=-2000000000;
	for (i=1;i<=n;i++)
		for (j=0;j<=p;j++)
		{
			for (k=0;k<=j;k++)
			{
				if (k==p) continue;
				f[i][j][1]=max(f[i][j][1],f[i-1][j-k][1]+chartA[i][k]);
				f[i][j][2]=max(f[i][j][2],f[i-1][j-k][2]+chartA[i][k]);
				f[i][j][2]=max(f[i][j][2],f[i-1][j-k][1]+chartB[i][k]);
				if (f[i][j][1]>ans || f[i][j][2]>ans) ans=max(f[i][j][1],f[i][j][2]);
			}
		}
	int tot=0;
	for (i=1;i<=n;i++) tot+=chartA[i][0];
	for (i=1;i<=n;i++)
	{
		int t=tot,last=p;
		for (j=1;j<=m && last;j++)
			if (b[i][j]) t+=sc[i][j];
			else
			{
				t+=sc[i][j];
				last--;
			}
		if (t-chartA[i][0]>ans) ans=t-chartA[i][0];
	}
	printf("%d\n",ans);
	return 0;
}