PKU 3186 Treats for the Cows
http://poj.org/problem?id=3186
n個の食べ物が順番に並んでいて、最初それぞれの価値はviである。
これをn日間かけて一日一個売る。ただし、売れるのは並んでいる両端の食べ物のみで、売り始めてからt日目の品物iはvi*tの値段で売れる。
この条件での利益を最大化しろというような問題。
貪欲にそのとき売っているもののうち一番安いものを売ろうとしたらWA。
n日目に残っている品物の範囲でdpしました。
nの大きさの勘違いとかなんやらでREやWAを出しました。
ll dp[2001][2000]; int in[2000]; main(){ int n; cin>>n; rep(i,n)cin>>in[i]; ll ans=0; rep(i,n-1){ for(int j=0;j<=i+1;j++){ if(j)dp[i+1][j]=max(dp[i+1][j],dp[i][j-1]+in[j-1]*(i+1)); if(j+n-1-i<n)dp[i+1][j]=max(dp[i+1][j],dp[i][j]+in[n-i-1+j]*(i+1)); } } rep(i,n)ans=max(ans,dp[n-1][i]+n*in[i]); cout<<ans<<endl; }