(POJ - 3186) treatments for the cows (interval DP)

Topic link ：3186 -- Treats for the Cows

The question ： Here you are. n Numbers that have been arranged , Each time you can take out the leftmost number or the rightmost number , altogether n Take the next time . Suppose you i The number taken next is x, You can get i*x The value of . You need to plan the retrieval sequence , Maximize the total value obtained .

analysis ： This problem is easy to be mistaken for greed , Select the minimum value that can be selected each time , Such greedy thinking is wrong .

The following is the analysis of the correct idea ：

We set up dp[i][j] It means to take it out from the left i Take them out from the right j In all cases, the result is the maximum , This state can be transferred from two states , One is dp[i-1][j], That is, take it out from the left i-1 Take them out from the right j Circumstances , That is to say, the next number we want to take is i Number , The other is dp[i][j-1], That is, take it out from the left i Take them out from the right j-1 Circumstances , Then the next number we want to take is number n-j+1 Number. , It can only be transferred by these two situations , Then the state transition equation is easy to write , Namely

for(int i=0;i<=n;i++)
	for(int j=0;i+j<=n;j++)
	{
		if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i]*(i+j));// Currently selected No i Elements  
		if(j>0) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[n-j+1]*(i+j));// Currently selected No n-j+1 Elements  
	}

Attention should be paid to the boundary problem , Nothing else , The complete code is attached below ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=2003;
int dp[N][N];//dp[i][j] It means taking from the left i The number is taken from the right j The maximum number of 
int a[N]; 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<=n;i++)
	for(int j=0;i+j<=n;j++)
	{
		if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i]*(i+j));// Currently selected No i Elements  
		if(j>0) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[n-j+1]*(i+j));// Currently selected No n-j+1 Elements  
	}
	int ans=0;
	for(int i=0;i<=n;i++)
		ans=max(ans,dp[i][n-i]);
	printf("%d",ans);
	return 0;
}