PKU 1036 Gangsters
http://poj.org/problem?id=1036
あるレストランに時間tiに価値piを持ったギャングが来る。
このギャングはドアがsi個?開かれていればレストランに入る。
ドアは1単位時間で一個開けるか閉めるか、そのままにするかに出来る。
レストランに入っているギャングの価値の合計を最大化しろというような問題。
動的計画法。
同じ時間には複数のギャングが入場可能なようです。
あと、sort(in,in+n)とやっていてひとつ足りなくてWAしまくりました。
int dp[200]; pair<int,PI> in[200]; main(){ int n,k,t; cin>>n>>k>>t; rep(i,n)cin>>in[i+1].F; rep(i,n)cin>>in[i+1].S.F; rep(i,n)cin>>in[i+1].S.S; sort(in,in+n+1); int ans=0; rep(i,n+1)dp[i]=-(1<<28); dp[0]=0; for(int i=1;i<=n;++i){ rep(j,i){ if(in[i].F-in[j].F>=abs(in[i].S.S-in[j].S.S)){ dp[i]=max(dp[j]+in[i].S.F,dp[i]); ans=max(dp[i],ans); } } } cout<<ans<<endl; }