比赛 20101116 评测结果 AAAAAAWWWA
题目名称 打砖块 最终得分 70
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 10:20:01
显示代码纯文本
#include <fstream>

#define I_F "gamea.in"
#define O_F "gamea.out"
#define MAX 201

using namespace std;

long s[MAX][MAX];
short c[MAX][MAX];
short n,m,k;
long ans;

void Input();
void Ycl();
void Dyna();
void Output();

int main()
{
	Input();
	Ycl();
	Dyna();
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n>>m>>k;
	short i,j;
	char t;
	for (i=0; i<n; i++)
		for (j=0; j<m; j++)
		{
			fin>>s[i][j];
			fin>>t;
			if (t=='N')
				c[i][j]=1;
		}
	fin.close();
}

void Ycl()
{
	short i,j;
	for (i=0; i<m; i++)
		for (j=n-2; j>=0; j--)
			if (c[j+1][i]<k)
			{
				s[j][i]+=s[j+1][i];
				c[j][i]+=c[j+1][i];
			}
			else
				c[j][i]=k+1;
}

void Dyna()
{
	short i,j,f;
	long t;
	long d[MAX][MAX]={{0}};
	for (i=1; i<=k; i++)
		for (f=0; f<n; f++)
			if (c[f][0]<=i)
			{
				d[i][0]=s[f][0];
				break;
			}
	for (i=1; i<=k; i++)
		for (j=1; j<m; j++)
		{
			t=d[i][j-1];
			for (f=0; f<n; f++)
				if (c[f][j]<=i)
					if (d[i-c[f][j]][j-1]+s[f][j]>t)
						t=d[i-c[f][j]][j-1]+s[f][j];
			d[i][j]=t;
		}
	ans=d[k][m-1];
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}