AtCoder Beginner Contest 163 E Active Infants 区间动归dp

AtCoder Beginner Contest 163   比赛人数11548  惨,比赛开始后28分钟看到所有题

AtCoder Beginner Contest 163  E  Active Infants  区间动归dp

总目录详见https://blog.csdn.net/mrcrack/article/details/104454762

在线测评地址https://atcoder.jp/contests/abc163/tasks/abc163_e

思路同https://www.cnblogs.com/zdragon1104/p/12734682.html

样例数据生成如下

4
1 3 4 2

20

注意，数值自小到大插入

插入数值1(初始位置1)
dp[1][1]=0
dp[2][2]=1
dp[3][3]=2
dp[4][4]=3

插入数值2(初始位置4)
dp[1][2]=7
dp[2][3]=6
dp[3][4]=5

插入数值3(初始位置2)
dp[1][3]=10
dp[2][4]=12

插入数值4(初始位置3)
dp[1][4]=20

AC代码如下

#include <cstdio>
#include <algorithm>
#define maxn 2005
#define LL long long
using namespace std;
LL dp[maxn][maxn];
struct node{
	int seq,val;
}a[maxn];
int cmp(node a,node b){
	return a.val<b.val;
}
int main(){//大的值最后放
	int i,j,len,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i].val),a[i].seq=i;
	sort(a+1,a+1+n,cmp);//按值自小到大排序
	for(i=1;i<=n;i++)dp[i][i]=(LL)a[1].val*abs(a[1].seq-i);//神奇的初始化
	for(len=2;len<=n;len++)//区间长度
		for(i=1;i+len-1<=n;i++){//左边界
			j=i+len-1;//右边界
			dp[i][j]=max(dp[i+1][j]+(LL)a[len].val*abs(a[len].seq-i),dp[i][j-1]+(LL)a[len].val*abs(a[len].seq-j));
		}
	printf("%lld\n",dp[1][n]);
	return 0;
}