Posted on 2012-03-29 11:37
C小加 閱讀(1738)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告
題意：賓館有個(gè)可以伸縮的門(mén)，每秒鐘可以伸長(zhǎng)1個(gè)單位，或者縮小1個(gè)單位，或者原地不動(dòng)。有N個(gè)強(qiáng)盜，每個(gè)強(qiáng)盜會(huì)在t的時(shí)間內(nèi)到達(dá)并按，如果此時(shí)門(mén)的開(kāi)方度和他的身材s正好相等，這個(gè)強(qiáng)盜就會(huì)進(jìn)來(lái)，然后你就能得到p的加分。
初始狀態(tài)門(mén)是關(guān)閉的，讓你求出在t時(shí)刻得到的最大得分。
分析：按時(shí)間從小到大排序，t時(shí)間內(nèi)最大的得分由t之前的時(shí)刻決定，滿(mǎn)足無(wú)后效性，每一個(gè)時(shí)刻都能得到最優(yōu)解，滿(mǎn)足最有子結(jié)構(gòu)，所以DP。
F[i]表示第i個(gè)人。
當(dāng)身材之差小于時(shí)間之差時(shí)F[i]=max(f[i],f[j]+ple[i].p) 0<=j<i 但得滿(mǎn)足一個(gè)條件，第j個(gè)人已經(jīng)進(jìn)去，否則門(mén)伸長(zhǎng)的寬度可能會(huì)小于身材。
#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)
//下一步做差的基礎(chǔ)是第j個(gè)人已經(jīng)進(jìn)去。
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;
}