[USACO21DEC Gold A] Paired Up

3
houzhiyuan LV 6 MOD @ 2021-12-22 14:31:32
因为有的需要求最大，有的需要求最小，考虑用 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]*_); }
- cqh @ 2021-12-22 14:46:27
  
  TQL
- yanbo @ 2021-12-22 15:43:47
  
  TQL %%%
- Samsara_soul @ 2021-12-26 18:32:37
  
  orz hzy