【学习笔记】[USACO21DEC] Paired Up P

本文主要是介绍【学习笔记】[USACO21DEC] Paired Up P，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

感觉对错算的理解还不够

对于 $T = 1$ ，将第一组的坐标排列成 ${x_i\}$ ，第二组的坐标排列成 ${y_i\}$ ，则一定是从小到大两两之间配对最优，这里的 DP 不用考虑合法性（不合法的一定不优），因此不用记录额外的状态，复杂度 $O(n^2)$

对于 $T = 2$ ，需要考虑合法性。设第一组没有被配对的坐标为 ${x_i\}$ ，第二组没有被配对的 ${y_i\}$ ，则这组坐标合法的充要条件为：

对于每对 $x_i,y_j)$ ，满足 $x_i-y_j>K\ \lor\ x_i-y_j<-K$

考虑其等价的判定方式，即加入一个数 $x_i$ ，对于所有存在的 $y_j$ 满足 $x_i>y_j+K$ ；加入一个数 $y_i$ ，对于所有存在的 $x_j$ 满足 $y_i>x_j+K$ 。

注意到条件： $x_i,y_i$ 是按照从小到大的顺序加入的，可以证明这个判定 虽然错算了一些东西，但是可以得到答案。

因此，记录之前选择的 $x_i,y_i$ 的最大值，转移可以 $O (1)$ 完成，复杂度 $O(n^4)$ 。

进一步发现， $x_i,y_i$ 之差一定超过 $K$ ，因此较小的那个不会产生限制，设 $dp_{i,j,k}$ 表示考虑完第一组的前 $i$ 个数，第二组的前 $j$ 个数，没有被配对的坐标最大的牛的编号为 $k$ 时没被配对的牛的重量之和的最大值（这样更好算贡献）。其中 $k\in [1,cnt_1]$ 表示第一组中的牛， $k\in [cnt_1+1,cnt_1+cnt_2]$ 表示第二组中的牛。这样我们将状态数优化到 $O(n^3)$ 。

考虑 进一步优化状态数。 注意到，转移过程中多次到达了 $k=i\ \lor cnt_1+j$ 的状态，因此我们只保留这些状态，然后加速转移过程。

转移过程可以 $O(n^2)$ 预处理。

更好的方法是定义 $f_{i,j,0/1}$ 表示钦定下一个不选的牛在第一/二组时的答案，这样每一次切换 $0/1$ 状态时只要平移若干步即可，比较好实现。

总复杂度 $O(n^2)$ 。

$\text{remark}$ 搞不懂那些一来就讲 $O(n^2)$ 做法的人是怎么想到的。。。

写代码的时候有点迷糊，感觉想不太清楚加速转移的过程。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
int type,n,K;
int cnt1,cnt2,lst[N][N],nxt[N];
ll dp[N][N],f[N][N],g[N][N],sm;
struct node{int x,w;
}a[N],b[N],c[N];
string str;
void chmax(ll &x,ll y){x=max(x,y);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>type>>n>>K;for(int i=1;i<=n;i++){int x,w;cin>>str>>x>>w,sm+=w;if(str[0]=='G'){a[++cnt1]={x,w};}else{b[++cnt2]={x,w};}}if(type==1){for(int i=1;i<=cnt1;i++){for(int j=1;j<=cnt2;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(abs(a[i].x-b[j].x)<=K)dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i].w+b[j].w);}}cout<<sm-dp[cnt1][cnt2];}else{memset(f,-0x3f,sizeof f),memset(g,-0x3f,sizeof g);f[0][0]=g[0][0]=0;int j=1;for(int i=1;i<=cnt2;i++){while(j<=cnt1&&a[j].x<=b[i].x+K)j++;nxt[cnt1+i]=j;}j=1;for(int i=1;i<=cnt1;i++){while(j<=cnt2&&b[j].x<=a[i].x+K)j++;nxt[i]=j;}for(int i=cnt1-1;i>=0;i--){for(int j=cnt2-1;j>=0;j--){lst[i][j]=(abs(a[i+1].x-b[j+1].x)<=K)?lst[i+1][j+1]+1:0;}}for(int i=0;i<=cnt1;i++){for(int j=0;j<=cnt2;j++){if(i+1<=cnt1)chmax(f[i+1][j],f[i][j]+a[i+1].w);if(j+1<=cnt2)chmax(g[i][j+1],g[i][j]+b[j+1].w);if(i+1<=cnt1&&j+1<=cnt2&&abs(a[i+1].x-b[j+1].x)<=K){chmax(f[i+1][j+1],f[i][j]);chmax(g[i+1][j+1],g[i][j]);}if(i+1<=cnt1){int p=max(0,nxt[i+1]-j-1);if(lst[i+1][j]>=p){chmax(g[i+1+p][j+p],f[i][j]+a[i+1].w);}}if(j+1<=cnt2){int p=max(0,nxt[j+1+cnt1]-i-1);if(lst[i][j+1]>=p){chmax(f[i+p][j+1+p],g[i][j]+b[j+1].w);}}}}cout<<max(f[cnt1][cnt2],g[cnt1][cnt2]);}
}