Brief description :

将数列 {an} 划分成一些长度在 [l, r] 之间的子段，每个子段的得分等于首尾项的和。（注意是完美划分，不要留空隙。~）

Note :

单调队列练习题。。
dp[i] = max{dp[j] + a[j+1]} + a[i] | j 要满足条件
把 dp[i] 和 a[i+1] 存在一起简化维护。。

#include 
using namespace std;
const int INF = 0x7fffffff;
const int N = 500002;

int a[N], d[N], q[N], cz, op;
int n, l, r;

void push(int x){
    while (cz <= op && d[x] >= d[q[op]])
        op--;
    q[++op] = x;
}

void init(){
    scanf("%d%d", &l, &r);
    for (int i=1;i<=n;i++) scanf("%d", &a[i]);
    a[n+1] = 0;
}

void solve(){
    d[0] = a[1]; cz = 0, op = -1;

    for (int i=1;i> n){
        init(); solve();
        cout << d[n] << endl;
    }
}

External link :

http://acm.hit.edu.cn/judge/show.php?Proid=2941

Posted by xiaodao
Category: 日常