Logo yyhs_luyicheng的博客

博客

The Answer to T904(Paired_Up) 来源于王志超大牛

2023-06-04 20:24:39 By yyhs_luyicheng
#include<bits/stdc++.h>
using namespace std;
int s[100005],a[100005],b[100005],k;
int f[100005],g[100005],ans;
void work(int t,int hd,int tl)
{
    if(t==1)
    {
        if((tl-hd+1)%2==0)return;
        int Min=1e9+1;
        for(int i=hd;i<=tl;i+=2)Min=min(Min,b[i]);
        for(int i=hd+1;i<=tl;i+=2)if(a[i+1]-a[i-1]<=k)Min=min(Min,b[i]);
        ans+=Min;return;
    }
    f[tl]=b[tl];f[tl-1]=0;g[tl]=0;g[tl-1]=max(b[tl-1],b[tl]);
    for(int i=tl-2;i>=hd;i--)
    {
        g[i]=f[i+1];
        if((s[i]-i-1)%2==1)g[i]=max(g[i],f[s[i]]+b[i]);
        else if(a[s[i]]-a[s[i]-1]<=k)
             {
                g[i]=max(g[i],f[s[i]+1]+b[i]);
                if(a[s[i]+1]-a[s[i]-1]<=k)g[i]=max(g[i],g[s[i]]+b[i]);
             }
        f[i]=f[i+2];
        if((s[i]-i-1)%2==0)f[i]=max(f[i],f[s[i]]+b[i]);
        else if(a[s[i]]-a[s[i]-1]<=k)
             {
                f[i]=max(f[i],f[s[i]+1]+b[i]);
                if(a[s[i]+1]-a[s[i]-1]<=k)f[i]=max(f[i],g[s[i]]+b[i]);
             }
         if(a[i+2]-a[i]<=k)
            if((s[i+1]-i-2)%2==1)f[i]=max(f[i],f[s[i+1]]+b[i+1]);
             else if(a[s[i+1]]-a[s[i+1]-1]<=k)
                {
                    f[i]=max(f[i],f[s[i+1]+1]+b[i+1]);
                    if(a[s[i+1]+1]-a[s[i+1]-1]<=k)f[i]=max(f[i],g[s[i+1]]+b[i+1]);
                 }
    }
    ans+=f[hd];return;
}
int main()
{
    int t,n;scanf("%d%d%d",&t,&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);

    a[n+1]=2e9+1;int pt=2;for(;pt<=n+1&&a[pt]-a[1]<=k;pt++);s[1]=pt;
    for(int i=2;i<=n;i++){for(;pt<=n+1&&a[pt]-a[i]<=k;pt++);s[i]=pt;}
    int h=1;
    for(int i=1;i<=n;)
    {
        while(i<n&&a[i+1]-a[i]<=k)i++;
        work(t,h,i);
        h=++i;
    }
    cout<<ans<<endl;
}

评论

ljxx_xuzihan
@yyhs_luyicheng 请规范使用Markdown和LaTeX,谢谢。
yyhs_qihongzhe
严重压行
yyhs_yaoyifan
@yyhs_wuzichen@yyhs_luyicheng 马蜂太酷了
yyhs_luyicheng
童鞋们,不要差评了!