526互联

USACO21DEC-Gold/洛谷P7987 Paired Up

发布时间 2023-04-20 22:24:27作者: SkyNet-PKN

涉及知识点：动态规划

题目链接

题意

给你一个数轴，数轴上有\(n\)个点，选其中一些点进行两两配对，配对要求是这两个点之间距离不能超过\(k\)，且一个点只能有一组配对，使得未配对的点之间无法再进行配对。每个点有个代价\(y_i\)，我们称一种配对方案的代价为未配对的点的代价和，求配对方案的最大或最小代价

分析

求最值，数据范围只能过\(O(n\log n)\)以下，很有可能是动态规划，我们分成两种情况讨论

T=1，求最小

由于代价的来源是未选择的点，所以我们在处理的时候应该反过来思考，我们不是去选点来配对，而是给一些点打上标记，让剩下没有标记的点都能配对，而我们要保证的事就是标记点之间距离必须大于\(k\)，而为了使剩下的点都能配对，显然相邻的两点配对最优

我们将状态设为 \(f[i][j]\) 表示处理完前\(i\)头奶牛，其中标记了 \(j\) 头牛（不配对），剩下 \((i-j)\) 头牛没有被标记（两两配对）。那么我们就可以进行如下分类讨论：

  • 如果\((i-j)\)为偶数，说明前面未标记的牛都已经配对了

    • 给第\(i\)个点打上标记，这样做没有任何限制
    • 不打标记，那么这个点和下一个点匹配，这样做需要保证 \(i\) 到 \(i+1\) 距离小于等于\(k\)

  • 如果\((i-j)\)为奇数，由于我们是相邻点之间进行配对，此时说明最后一个点（即第\(i-1\)个点）还找不到对象（雾）

    • 给第\(i\)个点打上标记，那么上一个点和下一个点匹配，这样做需要保证 \(i-1\) 到 \(i+1\) 的距离小于等于\(k\)
    • 不打标记，那么这个点和上一个点匹配，这样做需要保证 \(i-1\) 到 \(i\) 的距离小于等于\(k\)，但在讨论 \(i-1\) 时已经保证了此条件，不用再判断

    思维误区：有人会问如果第\(i-1\)的点被打了标记怎么办，但是此时\((i-j)\)为偶数。可以证明\((i-j)\)为奇数时第\(i-1\)个点不可能被打上标记

但是，这样空间复杂度是\(O(n^2)\)的，过不去\(10^5\)的数据，怎么改进？

注意到一点，得知\((i-j)\)的奇偶性不一定需要知道 \(j\) 具体的数值，只需要记录 \(i\) 和 \(j\) 的奇偶性，当 \(i\) 与 \(j\) 奇偶性相反时，\((i-j)\)为奇数，反之为偶数

那么我们引出一个新的变量 \(j'\)，表示 \(j\) 的奇偶性。\(i\) 和 \(j\) 奇偶性相同，表示\((i-j)\)为偶数的情况，也就是剩下的牛都配对了的情况（我们称其为“完整的”；\(f[i][!j']\) 意味着 \(i\) 和 \(j\) 奇偶性相反，表示\((i-j)\)为奇数的情况，也就是剩下的牛还差最后一个没有被配对的情况（我们称其为“残缺的”）。这样 \(f\) 数组就只用开 \(10^5\times 2\) 的大小了

我们重新思考具体的状态转移怎么写，依旧分类讨论（顺序与上文分类讨论相同）：

（我们令 \(last\) 表示【到 \(i\) 距离大于 \(k\) 的最大的点】）

b=i%2;
f[i][b]=min(f[i][b],f[last][b^1]+cow[i].second);//f[i][b]:i的完整状态 f[last][b^1]:由于标记之间距离需要大于k，所以从last转移；又由于j-1，所以b的奇偶性改变（从b变为b^1）
if(cow[i+1].first-cow[i].first<=k) f[i][b^1]=min(f[i][b^1],f[i-1][b^1]);//f[i][b^1]:i的残缺状态 f[i-1][b^1]:i-1的完整状态（i减一过后奇偶性发生变化）
if(cow[i+1].first-cow[i-1].first<=k) f[i][b^1]=min(f[i][b^1],f[last][b]+cow[i].second);//f[i][b^1]:i的残缺状态 f[last][b^1]:由于标记之间距离需要大于k，所以从last转移；又由于j-1，所以b的奇偶性改变（从b^1变为b）
f[i][b]=min(f[i][b],f[i-1][b]);//f[i][b]:i的完整状态 f[i-1][b]:i-1的残缺状态（原因同上）

最后，由于 \(n\) 为奇数时为了能两两匹配，\(j\) 为奇数，反之 \(j\) 为偶数，输出f[n][n%2]即可

T=2，求最大

很简单，将T=1时的代价全部乘以 \(-1\)，输出答案时再乘回来即可

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int t,n,k,f[MAXN][2],last;
pair<int,int>cow[MAXN];
int main(){
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	cin>>t>>n>>k;
	if(t==2) t=-1;
	for(int i=1;i<=n;i++){
		cin>>cow[i].first>>cow[i].second;
		cow[i].second*=t;
	}
	cow[0].first=numeric_limits<int>::min()+1;
	cow[n+1].first=numeric_limits<int>::max()-1;
	for(int i=1,b;i<=n;i++){
		while(cow[i].first-cow[last+1].first>k) last++;
		b=i%2;
		f[i][b]=min(f[i][b],f[last][b^1]+cow[i].second);
		if(cow[i+1].first-cow[i].first<=k) f[i][b^1]=min(f[i][b^1],f[i-1][b^1]);
		f[i][b]=min(f[i][b],f[i-1][b]);
		if(cow[i+1].first-cow[i-1].first<=k) f[i][b^1]=min(f[i][b^1],f[last][b]+cow[i].second);
	}
	cout<<f[n][n%2]*t<<endl;
	return 0;
}