题解 P2858 【[USACO06FEB]奶牛零食Treats for the Cows】

YoungLove · 2017-09-24 07:43:51 · 题解

Youngsc

裸裸的区间DP。

我们定义f[i][j]为卖掉i到j之间的临时得到的最大收益。

另外对与临时的价格我们做一个前缀和。

转移方程就应该是f[i][j]=max(f[i][j-1],f[i+1][j])+dis[j]-dis[i-1]貌似跟楼下的不是很一样。

这是什么意思呢

既然是买点i到j之间的，那么这一天卖掉的一定是i或j，同时因为多了一天，所以我之前卖的应该滞后一天卖，也就是说每一个物品再增加一个单价，同时加上我现在卖出去的i或j，去一个较大值就可以了。

代码在这里。

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long

using namespace std;

int n,m,f[2010][2010],dis[2010],a[2010];

inline void in(R int &a){
    R char c = getchar();R int x=0,f=1;
    while(!isdigit(c)){if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline int yg(){
    in(n);
    for(R int i=1; i<=n; ++i) in(a[i]),dis[i]=a[i]+dis[i-1];
    for(R int i=n; i>=1; --i)
        for(R int j=i; j<=n; ++j)
            f[i][j]=max(f[i][j-1],f[i+1][j])+dis[j]-dis[i-1];
    printf("%d",f[1][n]);
    return 0;
}

int youngsc = yg();
int main(){;}

（减少代码复制，共创美好洛谷）