自动搬运

查看原文

来自洛谷，原作者为

	houzhiyuan 花谢花飞花满天，红消香断有谁怜？

搬运于2025-08-24 22:34:56，当前版本为作者最后更新于2021-12-27 13:46:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更垃圾的阅读体验

因为有的需要求最大，有的需要求最小，考虑用 dp 解决。

考虑如果选择了一些奶牛要叉掉，首先需要满足这些叉掉的奶牛之间的距离需要大于 $k$，然后还要满足剩下奶牛可以匹配。

为了使剩下的奶牛尽量可以匹配，显然相邻两个匹配最优。

设 $f_{i,j}$ 表示已经做完了前 $i$ 头奶牛，叉掉了的奶牛数是奇数头还是偶数头（$j=0$ 表示偶数，$j=1$ 表示奇数）的最大或最小值。

那么通过 $i,j$ 的奇偶性，就可以判断出 $i$ 前面选择了的奶牛数量的奇偶性。

直接分情况转移，记录 $las$ 表示满足 $las$ 到 $i$ 的距离大于 $k$ 的最大的 $las$。

• 前面选择了偶数头奶牛，那么必然可以两两匹配，如果叉掉这头奶牛，那么就是 $f_{las,1-j}+y_i$，如果选择这头奶牛，这头奶牛需要与后面的进行匹配，因此需要满足 $i$ 到 $i+1$ 距离小于等于 $k$ ，如果满足，就转移 $f_{i-1,j}$。

• 前面选择了奇数头奶牛，那么必然剩下一头奶牛没有匹配，如果叉掉这头奶牛，需要让前一头奶牛与后面一头奶牛匹配，因此需要满足 $i-1$ 到 $i+1$ 距离小于等于 $k$，那么转移 $f_{las,1-j}+y_i$，如果选择这头奶牛，这头奶牛需要与前面的进行匹配，因此需要满足 $i-1$ 到 $i$ 距离小于等于 $k$ ，如果满足，就转移 $f_{i-1,j}$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,k,f[N][2],_=1,las;
struct hzy{int x,y;}a[N];
void get(int &x,int y){x=x<y?x:y;}
void getmax(int &x,int y){x=x>y?x:y;}
int main(){
	scanf("%d%d%d",&T,&n,&k);
	if(T==2)_=-1;
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),a[i].y*=_;
	a[0].x=-1e9,a[n+1].x=2e9;
	memset(f,63,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		while(a[i].x-a[las+1].x>k)las++;
		int z=i&1;
		get(f[i][z],f[las][z^1]+a[i].y);
		if(a[i].x-a[i-1].x<=k)get(f[i][z],f[i-1][z]);
		if(a[i+1].x-a[i-1].x<=k)get(f[i][z^1],f[las][z]+a[i].y);
		if(a[i+1].x-a[i].x<=k)get(f[i][z^1],f[i-1][z^1]);
	}	
	if(n&1)printf("%d",f[n][1]*_);
	else printf("%d",f[n][0]*_);
}