【O - Treats for the Cows】

2019/7/23 12:07:01 人评论 次浏览 分类:学习教程

思路:

  • 新类型:区间dp
  • dp[l][r] 代表在区间 [l,r] 内可以取到的最大值,注意,我们是从小到大逐步蚕食增大区间的,根据题意,可知在整个过程中是最后取本区间内的值。
  • 注意初始化,枚举时先枚举长度,再根据长度枚举起点。

代码:

  • 47ms 14560kB
//47ms		14560kB


#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2005;

int N;
int A[maxn];
int dp[maxn][maxn];

void SOLVE(){
	for(int i=1;i<=N;i++)
		dp[i][i] = A[i] * N;
	for(int len = 1 ; len < N ; len++)
		for(int l = 1 ; l <= N-len ; l++)
			dp[l][l+len] = max(dp[l][l+len-1] + A[l+len]*(N-len) , dp[l+1][l+len] + A[l]*(N-len));
	return ;
}

int main(){
	cin>>N;
	for(int i=1;i<=N;i++)
		cin>>A[i];
	SOLVE();
	cout<<dp[1][N]<<endl;
	return 0;
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->