| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一维Dp不就好了嘛……#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int N,K,T,width=0,data[101],ans=0;
bool visit[101];
struct Ganster
{
int t,p,s;
};
Ganster g[101];
inline bool operator<(const Ganster & g1, const Ganster & g2)
{
return g1.t==g2.t ? (g1.s==g2.s ? g1.p<g2.p : g1.s<g2.s) : g1.t<g2.t;
}
int main()
{
scanf("%d%d%d",&N,&K,&T);
g[0].t=g[0].s=g[0].p=-1;visit[0]=true;
for(int i=1;i<=N;i++){scanf("%d",&g[i].t);}
for(int i=1;i<=N;i++){scanf("%d",&g[i].p);}
for(int i=1;i<=N;i++){scanf("%d",&g[i].s);}
sort(g,g+N+1);g[0].t=g[0].s=g[0].p=data[0]=0;
for(int i=1;i<=N;i++)
{
for(int j=0;j<i;j++)
{
if(visit[j])
{
if(g[i].t-g[j].t>=abs(g[i].s-g[j].s))
{
data[i]=max(data[i],data[j]+g[i].p);
}
}
}
visit[i]=(bool)data[i];
ans=max(ans,data[i]);
}
cout<<ans<<endl;
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator