比赛 20101116 评测结果 AAAAWWWWWA
题目名称 打砖块 最终得分 50
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 10:08:03
显示代码纯文本
#include <cstdio>
const int MAXN=205;
const int inf=0x7fffffff;

inline void Max(int &a,int b)
{
	if (b>a) a=b;
}

int N,M,K;
int d[MAXN][MAXN][MAXN];
int cost[MAXN][MAXN],w[MAXN][MAXN];
char c[MAXN][MAXN];

int main()
{
	freopen("gamea.in","r",stdin);
	freopen("gamea.out","w",stdout);
	scanf("%d%d%d",&N,&M,&K);
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			scanf("%d %c",w[j]+i,c[j]+i);
		//	printf("%d %c ",w[j][i],c[j][i]);
			cost[j][i]=cost[j][i-1]+(c[j][i]=='N');
			w[j][i]+=w[j][i-1];
		}
		//printf("\n");
	}
	for(int i=1;i<=M;i++)
		for(int j=0;j<=N;j++)
			for(int k=0;k<=K;k++)
			{
				d[i][j][k]=-inf;
				int c=cost[i][N]-cost[i][j];
				if (k>=c)
					d[i][j][k]=d[i-1][N][k-c]
						+w[i][N]-w[i][j];
				if (j>=1)Max(d[i][j][k],d[i][j-1][k]);
			}
	printf("%d\n",d[M][N][K]);
	return 0;
}