P2034 选择数字

题目描述

给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。

---

错误日志： longlong 的 \(inf\) 没有设为 0xfffffffffffffff

---

Solution

正难则反

正难则反

复习看到了双倍经验就回来看看

求最大值有点难， 转化为求最小去除值

设 \(dp[i]\) 为 \(i\) 为断点， 考虑到 \(i\) 处的最小去除值

发现每隔 \(K + 1\) 必有一个断点

所以 \(dp[i] = \min_{j = i - k - 1}^{i - 1}dp[j] + a[i]\)

然后单调队列优化， 答案在区间 \([n - K, n]\) 内

总值减一下即可

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(LL i = (x);i <= (y);i++)

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const LL maxn = 200019, inf = 0xfffffffffffffff;

LL num, K;

LL a[maxn], sum;

LL dp[maxn];

struct Que{

	LL Index, val;

	}Q[maxn];

LL head = 1, tail;

void push_back(LL Index, LL val){

	while(head <= tail && Q[tail].val >= val)tail--;

	Q[++tail] = (Que){Index, val};

	}

LL get_min(LL p){

	while(head <= tail && p - Q[head].Index > K + 1)head++;

	return Q[head].val;

	}

void init(){

	num = RD(), K = RD();

	REP(i, 1, num)a[i] = RD(), sum += a[i];

	memset(dp, 127, sizeof(dp));

	push_back(0, 0);

	}

void solve(){

	REP(i, 1, num){

		dp[i] = get_min(i) + a[i];

		push_back(i, dp[i]);

		}

	LL ans = inf;

	REP(i, num - K, num)ans = min(ans, dp[i]);

	printf("%lld\n", sum - ans);

	return ;

	REP(i, 1, num)printf("%lld ", dp[i]);

	}

int main(){

	init();

	solve();

	return 0;

	}