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