这真的是一道神题，或许是因为我之前没有见过这个方法的缘故吧
感觉对 错算 的理解还不够
对于$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)$做法的人是怎么想到的。。。
写代码的时候有点迷糊，感觉想不太清楚加速转移的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #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]);
}
}
|