比赛 20101116 评测结果 AAAAWWTTTA
题目名称 打砖块 最终得分 50
用户昵称 郭乾乐 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 10:41:53
显示代码纯文本
#include<iostream>
#include<fstream>
using namespace std;
int n,m,s[201][201],ff[201][201],c[201][201],f[201][201][201];
bool pan[201][201][201];
int minn(int a,int b)
{
	if(a>b) return b;
	else return a;
}
int maxn(int a,int b)
{
	if(a>b) return a;
	else return b;
}
int dfs(int l,int r,int k)
{
	if(l>m||r>n||k==0) return 0;
	if(pan[l][r][k]) return f[l][r][k];
	pan[l][r][k]=true;
	int t=minn(k,n);
	for(int i=0;i<=t;i++)
		for(int j=1;j<=m;j++)
			    f[l][r][k]=maxn(f[l][r][k],s[j][i]+dfs(j,i,k-t+c[j][i]));
	pan[l][r][k]=false;
	return f[l][r][k];
}

int main()
{
    ifstream fin("gamea.in");
	ofstream fout("gamea.out");
	int i,j,k,zi;
	char x;
	bool p=true;
	fin>>n>>m>>zi;
	for(i=1;i<=m;i++)
	{
		c[i][0]=0;
		s[i][0]=0;
	}
	for(i=n;i>=1;i--)
		for(j=1;j<=m;j++)
		{
			fin>>s[j][i]>>x;
			if(x=='Y')
			{
				p=false;
				c[j][i]=1;
			}
			else
				c[j][i]=0;
		}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			s[j][i]+=s[j][i-1];
			c[j][i]+=c[j][i-1];
		}
	if(!p)
	{
		int mm=0;	
		for(i=0;i<=n;i++)
			mm=maxn(mm,dfs(1,i,zi-i+c[1][i]));
		fout<<mm;
		return 0;
	}
	else
	{
	    for(i=1;i<=zi;i++)
			for(j=1;j<=m;j++)
				for(k=0;k<=n;k++)
					if(i-k>=0&&ff[j][i]<ff[j-1][i-k]+s[j][k])
						ff[j][i]=ff[j-1][i-k]+s[j][k];
		fout<<ff[m][zi];
		return 0;
	}
}