区间dp P2858

Lucaster_ · 2019-06-03 14:29:39 · 题解

题目传送门

#include<cstdio>
#include<iostream>
#define N 2002
using namespace std;
int i,j,k,n,len,a[N],f[N][N];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) f[i][i]=a[i]*n;
    for(len=1;len<n;len++)
     for(i=1;i+len<=n;i++)
     {
        j=i+len;
        k=n-len;
        f[i][j]=max(f[i+1][j]+a[i]*k,f[i][j-1]+a[j]*k);
     }
    printf("%d",f[1][n]);
    return 0;
}

这道题非常不错的
一开始想开个三维数组f[i][j][k]表示i到j区间已经取完并且当前取到了第k个（用于计算权值）
2000^3，会M掉的

深思熟虑
想不出来换题吧

才怪
似乎不需要第三维啊
中间i到j这段区间一定是连续的（由题可得）
所以用n-已经取过的区间长度就是当前取得第几个

又因为这是一道区间dp 连续的区间

开两层循环控制开头结尾，直接去dp就好

核心部分：
for(len=1;len<n;len++)
 for(i=1;i+len<=n;i++)
 {
    j=i+len;
    k=n-len;
    f[i][j]=max(f[i+1][j]+a[i]*k,f[i][j-1]+a[j]*k);
 }

k就是我刚才说的，用总数－区间长度，就是当前取到了第几个

用k*a[i or j]就是本次的价值

每次不是从开头取就是结尾

开头取的价值：f[i+1][j]+a[i]*k;

结尾取的价值：f[i][j-1]+a[j]*k;

dp一下就好了

等等还没结束

注意这里：

for(i=1;i<=n;i++) f[i][i]=a[i]*n;

不加这个还真过不了

为啥嘞？

因为当你取到最后一个的时候，区间起点等于重点，且当前是最后一个取的，即第n个
所以f[i][i]就等于a[i]*n

大家都能看懂吧

完结撒花[~~~]

To管理大大：楼上大佬们都没有讲转移方程的原理，希望通过我这篇题解让更多人看到转移方程的原理