Posted on 2012-03-29 11:37
C小加 閱讀(1758)
評論(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;
}