luogu2858奶牛零食题解--区间DP

题目链接

https://www.luogu.org/problemnew/show/P2858

一句话题意:

https://cn.vjudge.net/problem/POJ-3186#author=Re0

分析

很显然这道题是不行滴,但是把这个数列看作从一个个区间倒着向外扩展取数而成的话,这样就保证了最优子结构和无后效性两个特点,于是就开始DP了

按照区间DP一贯的套路,先初始化元区间,也就是长度为1的区间值$f[i][i]=a[i] * n$,为什么要倒着取呢?前面已经说明了，这样保证状态无后效性

我们枚举区间长度为阶段,然后考虑决策就很简单了,考虑是向左边扩展还是右边扩展

1
2
3
4
5
6
7
for(ri len=2;len<=n;len++){//区间长度 
        for(l=1;l<=n-len+1;l++){
            r=l+len-1;
            f[l][r]=max(f[l+1][r]+a[l]*(n-len+1),f[l][r-1]+a[r]*(n-len+1));
            /*要么选左边的要么选右边的*/
        }
    }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=2005;
const int inf=0x7fffffff;
int f[maxn][maxn],n,a[maxn];
int main(){
    int l,r,ans=-inf;
    read(n);
    for(ri i=1;i<=n;i++){
        read(a[i]);
        f[i][i]=a[i]*n;
    }
    for(ri len=2;len<=n;len++){//区间长度 
        for(l=1;l<=n-len+1;l++){
            r=l+len-1;
            f[l][r]=max(f[l+1][r]+a[l]*(n-len+1),f[l][r-1]+a[r]*(n-len+1));
            /*要么选左边的要么选右边的*/
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}