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]);
}

実装もこれだけ。