比赛 |
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;
}
}