bzoj 1652: [Usaco2006 Feb]Treats for the Cows【区间dp】

2024-09-30 20:41:44

裸的区间dp，设f[i][j]为区间(i,j)的答案，转移是f[i][j]=max(f[i+1][j]+a[i](n-j+i),f[i][j-1]+a[j]*(n-j+i));

#include<iostream>

#include<cstdio>

using namespace std;

const int N=2005;

int n,a[N],f[N][N];

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

 	for(int i=n;i>=1;i--)

		for(int j=i;j<=n;j++)

			f[i][j]=max(f[i+1][j]+a[i]*(n-j+i),f[i][j-1]+a[j]*(n-j+i));

    printf("%d",f[1][n]);

    return 0;

}

最新文章

热门文章