P7987

houzhiyuan · 2021-12-27 13:46:28 · 题解

更垃圾的阅读体验

因为有的需要求最大，有的需要求最小，考虑用 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]*_);
}