P2627 修剪草坪

题目描述

在一年前赢得了小镇的最佳草坪比赛后，Farm John变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farm John希望能够再次夺冠。

然而，Farm John的草坪非常脏乱，因此，Farm John只能够让他的奶牛来完成这项工作。Farm John有N(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。

靠近的奶牛们很熟悉，因此，如果Farm John安排超过K只连续的奶牛，那么，这些奶牛就会罢工去开派对:)。因此，现在Farm John需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。

输入输出格式

输入格式：

第一行：空格隔开的两个整数 N 和 K

第二到 N+1 行：第 i+1 行有一个整数 E_i

输出格式：

第一行：一个值，表示 Farm John 可以得到的最大的效率值。

---

观察问题，转化为满足合法的条件下，舍去效率的点尽可能小

\(dp[i]\) 表示： 前 \(1 ~ i\) 满足条件合法， 且一定舍弃了第 \(i\) 个 舍去的最小效率

我们需要一点 动归中的贪心思想， 最后合法的方案一定是：选尽可能多个——一个断点——继续选连续的尽可能多的， 断点保证了连续的奶牛不大于 \(k\) 个，在这个条件下尽可能多选， 而我们的 \(dp[i]\) 弄的就是这样一个断点， 因为连续的牛不能超过 \(k\) 个，那么两断点之间应有什么联系呢？考虑边缘情况， \(i\) 和 \(j\)之间恰好夹着一个长度为 \(k\) 的区间，则有 \(i - j = k +1\) 所以我们得到 \(j\) 与 \(i\) 的关系： \(1 <= i - j <= k + 1\) 并得到状态转移方程$$dp[i] = min(dp[j]\ \ {1 <= i - j <= k + 1}) + v[i]$$

由于 \(min(dp[j]\ \ {1 <= i - j <= k + 1}\) 的取值在一个区间内， 考虑单调队列优化 \(dp\)。

推完所有 \(dp\) 后，考虑最后一个区间：最后一个区间合法，只要在 \(n - k\) 之后有断点即可（画图）， 所以我们枚举在 \(n - k\) 之后的每一个 \(dp\) 或者说直接可以利用刚才的的单调队列， 查询这段区间的最小值， 用全部权值减去这一最小值即为答案

附：考场小技巧：此题中出现大量端点问题， 比赛时多画图， 比凭空想端点来的快得多， 也稳

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

LL RD(){

	LL flag = 1, out = 0;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 = 100019;

LL num, k, sum;

LL dp[maxn];//表示前i个人的合法情况下的去掉的最小值

LL v[maxn];

struct Que{

	LL index, val;

	Que (LL index, LL val):index(index), val(val){}

	Que(){};

	}Q[maxn];

LL head = 1, tail = 0;

LL get_min(){return Q[head].val;}

void push_back(LL x){

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

	Q[++tail] = Que(x, dp[x]);

	}

void check(LL x){

	while(x - Q[head].index > k + 1)head++;

	}

int main(){

	num = RD();k = RD();

	for(LL i = 1;i <= num;i++)v[i] = RD(), sum += v[i];

	for(LL i = 1;i <= k + 1;i++)dp[i] = v[i], push_back(i);

	for(LL i = k + 2;i <= num;i++){

		check(i);

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

		push_back(i);

		}

	check(num + 1);

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

	return 0;

	}