题解：P15263 [USACO26JAN2] Circle of Cows P

swordofsky · 2026-11-12 12:09:37 · 题解

提示：本题可以选择相信评测机（小常数 O(n^3) 可以通过）。

找一找性质。

线段表示匹配。

乍一看蓝线匹配没有浅绿线匹配更优。然而事实真的如此吗？

蓝贡献：s1=\min(\min(a,b+c+d),\min(c,a+b+d))=\min(a,c)

绿贡献：s2=\min(\min(a+b,c+d),\min(a+d,b+c))=\min({a+b,c+d,a+d,b+c})>s1

所以交叉的两条线永远更优。我们选点应该选 l_1<l_2<……<l_k<r_1<r_2<……<r_k（比较的是断环为链后的值，l 为左指针，r 为右指针）。这样可以使点对连线尽可能交叉。

断环为链。选取两个端点，双指针贪心看看以这两个端点的距离 dis 作为距离最小值，最大可以匹配多少对点。

过程：当 \min(a_r-a_l,c-(a_r-a_l))<dis 时，判断。若 a_r-a_l<c-(a_r-a_l) 即两个指针靠得太近，r=r+1。否则两个指针靠得太远，l=l+1。

最后把答案当下标，最短距离 dis 存进数组，做一遍后缀和得到答案。

:::info[code]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005;
ll n,c,a[N],dp[N];
ll sol(ll x,ll y,bool &f){//解决距离，顺便判断哪个距离更近
    ll l=y-x,r=c-l;
    f=(l<r);
    return min(l,r);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i]+c;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){//开始双指针
            bool f;
            ll l=i+1,r=j+1,dis=sol(a[i],a[j],f),ans=1;
            while(l<j&&r<i+n){//计算答案
                while(l<j&&r<i+n&&sol(a[l],a[r],f)<dis){
                    if(f) r++;
                    else l++;
                }
                if(l==j||r==i+n) break;
                ans++;
                l++;
                r++;
            }
            dp[ans]=max(dp[ans],dis);
        }
    }
    for(int i=n/2;i>=1;i--){
        dp[i]=max(dp[i],dp[i+1]);
    }
    for(int i=1;i<=n/2;i++){
        cout<<dp[i]<<' ';
    }
    return 0;
}

:::