LG3004 「USACO2010DEC」Treasure Chest 区间DP+滚动数组优化

问题描述

LG3004

题解

把拿走的过程反向，看做添加的过程，于是很显然的区间DP模型。

设\(opt_{i,j}\)代表区间\([i,j]\)中Bessie可以获得的最大值，显然有

\[opt_{l,r}=sum_{l,r}-min(opt_{l+1,r},opt_{l,r+1})\]

于是爆了空间。

强行压成一维，滚动数组优化即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=5007;

int s[maxn],opt[maxn],n;

int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(opt[i]);s[i]=s[i-1]+opt[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len<=n+1;l++){
            int r=l+len-1;
            opt[l]=s[r]-s[l-1]-min(opt[l],opt[l+1]);
        }
    }
    printf("%d\n",opt[1]);
    return 0;
}