比赛 |
20101116 |
评测结果 |
AAAAWWWWWA |
题目名称 |
打砖块 |
最终得分 |
50 |
用户昵称 |
lc |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-11-16 11:07:18 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 210,maxm = 210,INF = 1000000000;
int N,M,K;
int Val[maxn][maxm],Point[maxn][maxm];
int Sval[maxm][maxn],Spo[maxm][maxn];
int F[maxm][maxn];
void prep()
{
scanf("%d%d%d\n",&N,&M,&K);
for (int i=1; i<=N; i++)
{
for (int j=1; j<=M; j++)
{
char ch;
scanf("%d %c",&Val[i][j],&ch);
Point[i][j] = (ch=='Y');
//printf("%d %d ",Val[i][j],Point[i][j]);
}
}
for (int i=1; i<=M; i++)
for (int j=N; j>=1; j--) Spo[i][j] = Spo[i][j+1] + Point[j][i];
for (int i=1; i<=M; i++)
for (int j=N; j>=1; j--) Sval[i][j] = Sval[i][j+1] + Val[j][i];
}
void work()
{
F[0][0] = 0;
for (int i=1; i<=M; i++)
for (int j=0; j<=K; j++)
for (int p=0; p<=N; p++)
{
int t = j - p + Spo[i][N-p+1];
if (t<0) continue;
if (F[i-1][t] + Sval[i][N-p+1] >F[i][j])
F[i][j] = F[i-1][t] + Sval[i][N-p+1];
}
printf("%d\n",F[M][K]);
}
int main()
{
freopen("gamea.in","r",stdin);
freopen("gamea.out","w",stdout);
prep();
work();
return 0;
}