Posted on 2012-03-29 11:37
C小加 阅读(1650)
评论(1) 编辑 收藏 引用 所属分类:
解题报告
题意：宾馆有个可以伸缩的门，每秒钟可以伸长1个单位，或者缩小1个单位，或者原地不动。有N个强盗，每个强盗会在t的时间内到达并按，如果此时门的开方度和他的身材s正好相等，这个强盗就会进来，然后你就能得到p的加分。
初始状态门是关闭的，让你求出在t时刻得到的最大得分。
分析：按时间从小到大排序，t时间内最大的得分由t之前的时刻决定，满足无后效性，每一个时刻都能得到最优解，满足最有子结构，所以DP。
F[i]表示第i个人。
当身材之差小于时间之差时F[i]=max(f[i],f[j]+ple[i].p) 0<=j<i 但得满足一个条件，第j个人已经进去，否则门伸长的宽度可能会小于身材。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXM=103;
typedef
struct People
{
int t,p,s;
}People;
People ple[MAXM];
int f[MAXM];
bool cmp(People p1,People p2)
{
return p1.t<p2.t;
}
int main()
{
int n,k,s;
scanf("%d %d %d",&n,&k,&s);
for(
int i=1;i<=n;++i)
scanf("%d",&ple[i].t);
for(
int i=1;i<=n;++i)
scanf("%d",&ple[i].p);
for(
int i=1;i<=n;++i)
scanf("%d",&ple[i].s);
sort(ple+1,ple+n+1,cmp);
f[0]=0;
ple[0].p=0;ple[0].s=0;ple[0].t=0;
int ans=0;
for(
int i=1;i<=n;++i)
{
for(
int j=i-1;j>=0;--j)
{
if(f[j]>=ple[j].p)
//下一步做差的基础是第j个人已经进去。
if(abs(ple[i].s-ple[j].s)<=ple[i].t-ple[j].t)
f[i]=max(f[i],f[j]+ple[i].p);
}
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}