做该题的时候,看了网上另外一个版本的递推关系,不过还是朴素一点的比较好理解.状态转移方程为:
f[i,j]=max{f[i-1,j-1],f[i-1,j],f[i-1,j+1]}+w(i,j), 其中f[i,j]表示第i 秒 ,门开放度为j 时的最大加分.w(i,j)表示在该状态下的所有加分.为防止超内存用滚动数组.(由于不仔细把1写成了i,调试了半天,杯具了~~) 详细见代码:
#include<iostream>
#include<algorithm>
using namespace std;
int f[2][102];
int hash[30002];
int N,K,T,ans;
typedef struct
{
int t,p,s;
}Gant;
Gant s[102];
int cmp(Gant a,Gant b)
{
if(a.t<b.t) return 1;
else if(a.t==b.t)
{
if(a.s<b.s) return 1;
}
return 0;
}
int main()
{
int i,j,k;
scanf("%d%d%d",&N,&K,&T);
for(i=1;i<=N;i++) scanf("%d",&s[i].t);
for(i=1;i<=N;i++) scanf("%d",&s[i].p);
for(i=1;i<=N;i++) scanf("%d",&s[i].s);
memset(hash,0,sizeof(hash));
memset(f,-1,sizeof(f));
for(i=1;i<=N;i++) hash[s[i].t]=1;
sort(s+1,s+N+1,cmp);
f[0][0]=0;
ans=0;
for(i=1;i<=T;i++)
for(j=0;j<=K;j++)
{
int w=0;
if(hash[i])
{
for(k=1;k<=N;k++)
if(s[k].t==i&&s[k].s==j)
w+=s[k].p;
}
if(j>=1&&f[(i-1)&1][j-1]!=-1&&f[i&1][j]<f[(i-1)&1][j-1]+w)
f[i&1][j]=f[(i-1)&1][j-1]+w;
if(j+1<=K&&f[(i-1)&1][j+1]!=-1&&f[i&1][j]<f[(i-1)&1][j+1]+w)
f[i&1][j]=f[(i-1)&1][j+1]+w;
if(f[(i-1)&1][j]!=-1&&f[i&1][j]<f[(i-1)&1][j]+w)
f[i&1][j]=f[(i-1)&1][j]+w;
if(ans<f[i&1][j]) ans=f[i&1][j];
}
printf("%d\n",ans);
return 0;
}
posted on 2010-08-09 17:43
wuxu 阅读(127)
评论(0) 编辑 收藏 引用 所属分类:
动态规划