POJ3186 Treat for the Cows
最初「辞書順最小の文字列をとってくればいいんじゃないか」とか勘違いして、嘘解法する。当然落とされる。
よく考えると、区間についてのDPができる。このタイプのDPはじめてだったので新鮮だった。良問だと思う。
#include<stdio.h> #include<algorithm> #include<vector> #include<deque> using namespace std; int dp[2000][2000]; int main() { int num; scanf("%d",&num); vector<int>vec; for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); vec.push_back(zan); } for(int j=0;j<num;j++) { for(int k=0;k<num-j;k++) { if(j==0) { dp[k][k]=num*vec[k]; } else { dp[k][k+j]=max(dp[k][k+j-1]+vec[k+j]*(num-j),dp[k+1][k+j]+vec[k]*(num-j)); } } } printf("%d\n",dp[0][num-1]); }
実装もこれだけ。