【USACO 2021DEC P】Paired Up
Description
数轴上总计有 \(N\)（\(1\le N\le 5000\)）头奶牛，每一头奶牛都是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一。第 \(i\) 头奶牛的品种为 \(b_i\in \{H,G\}\)，第 \(i\) 头奶牛的位置为 \(x_i\)（\(0 \leq x_i \leq 10^9\)），而第 \(i\) 头奶牛的重量为 \(y_i\)（\(1 \leq y_i \leq 10^5\)）。
根据 Farmer John 的信号，某些奶牛会组成对，使得
-
每一对包含位置相差不超过 \(K\) 的一头荷斯坦牛 \(h\) 和一头更赛牛 \(g\)（\(1\le K\le 10^9\)）；也就是说，\(|x_h-x_g|\le K\)。
-
每一头奶牛要么包含在恰好一对中，要么不属于任何一对。
-
配对是极大的；也就是说，没有两头未配对的奶牛可以组成对。
你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，
-
如果 \(T=1\)，计算未配对的奶牛的最小重量和。
-
如果 \(T=2\)，计算未配对的奶牛的最大重量和。
Input
输入的第一行包含 \(T\)，\(N\) 和 \(K\)。
以下 \(N\) 行，第 \(i\) 行包含 \(b_i,x_i,y_i\)。输入保证 \(0\le x_1<x_2<\cdots<x_{N}\le 10^9\)。
Output
输出未配对的奶牛的最小或最大重量和。
Sample Input
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
Sample Output
16
Data Constraint
- 测试点 4-7 满足 \(T=1\)；
- 测试点 8-14 满足 \(T=2\) 且 \(N\le 300\)；
- 测试点 15-22 满足 \(T=2\)。
Solution
一个重要的观察是：匹配是不交的
因为匹配相交显然可以交换，这样不会改变答案
这启发我们用dp解决问题
对于\(T=1\)，像最长公共子序列一样算就行了
对于\(T=2\)，这时我们发现，不能忽略最大匹配的条件了
设\(f,g\)分别表示钦定了下一次不选\(H,G\)牛
然后对于一头\(H\)牛，找到它之前最后一头\(G\)牛，使得其距离\(>k\)
那么如果能转移，中间的部分必须能全部匹配
这个判定显然可以预处理，于是复杂度\(O(N^2)\)
Code
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define INF 10000000000
#define LL long long
#define N 5010
#define M 1000000
int ty,n,k,tot=1,last[N];
int c[2][N],A,B,nxt[2][N],lst[N][N],f[N][N],g[N][N],sum;
struct point{int k,x,y;}a[N];
void upd(int&x,int y){x=max(x,y);}
int main(){
scanf("%d%d%d",&ty,&n,&k);
F(i,1,n){
char s[4];int x,y;
scanf("%s%d%d",s+1,&x,&y);
int t=s[1]=='G'?1:0;
sum+=y;
a[i]=(point){t,x,y};
}
F(i,1,n)a[i].k?c[1][++B]=i:c[0][++A]=i;
if(ty==1){
memset(f,128,sizeof(f));
f[0][0]=0;
F(i,0,A) F(j,0,B){
if(i+1<=A)upd(f[i+1][j],f[i][j]);
if(j+1<=B)upd(f[i][j+1],f[i][j]);
if(i+1<=A&&j+1<=B){
int x=c[0][i+1],y=c[1][j+1];
if(abs(a[x].x-a[y].x)<=k)upd(f[i+1][j+1],f[i][j]+a[x].y+a[y].y);
}
}
printf("%d",sum-f[A][B]);
}else{
F(i,1,A) F(j,1,B){
if(a[c[1][j]].x-a[c[0][i]].x>k)break;
nxt[0][i]=j;
}
F(i,1,B) F(j,1,A){
if(a[c[0][j]].x-a[c[1][i]].x>k)break;
nxt[1][i]=j;
}
memset(f,128,sizeof(f));
memset(g,128,sizeof(g));
f[0][0]=g[0][0]=0;
Fd(i,A,1) Fd(j,B,1){
if(abs(a[c[0][i]].x-a[c[1][j]].x)<=k)lst[i][j]=lst[i+1][j+1]+1;
}
F(i,0,A) F(j,0,B){
int n1=max(nxt[0][i]-j,0);
int n2=max(nxt[1][j]-i,0);
if(i+n1<=A&&lst[i+1][j+1]>=n1)upd(g[i+n1][j+n1],f[i][j]);
if(j+n2<=B&&lst[i+1][j+1]>=n2)upd(f[i+n2][j+n2],g[i][j]);
if(abs(a[c[0][i+1]].x-a[c[1][j+1]].x)<=k&&i+1<=A&&j+1<=B){
upd(f[i+1][j+1],f[i][j]);
upd(g[i+1][j+1],g[i][j]);
}
if(i+1<=A)upd(f[i+1][j],f[i][j]+a[c[0][i+1]].y);
if(j+1<=B)upd(g[i][j+1],g[i][j]+a[c[1][j+1]].y);
}
printf("%d",max(f[A][B],g[A][B]));
}
return 0;
}