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\),为什么要倒着取呢?前面已经说明了，这样保证状态无后效性

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

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));

            /*要么选左边的要么选右边的*/

        }

    }

代码

#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;

}

巴特西

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

题目链接

分析

代码

最新文章

热门文章