P7688 [CEOI2005] Ticket Office 题解

· · 题解

P7688 [CEOI2005] Ticket Office 题解

题目传送门。

思路

首先考虑尽可能多放置全价票。因为全价票和半价票占的大小相同。也就是说假设我们初始全部使用半价票，那么此时放上一个全价票最多需要去掉 2 张半价票，最少去掉 1 张。换句话说，换成全价票一定不劣。

所以我们尽可能多放置全价票是对的。至于放置多少张显然是好算的，能选就选即可。

但是，会发现一个问题，有可能我这个位置放了全价票，半价票就会少一张；而在另一个位置就不会少。所以能选就选的策略能且仅能算出全价票的数量，并不能确定在哪里放。换句话说，我们不知道最多能放多少张半价票。

于是考虑使用动态规划计算。设 f_i 表示后 i 个位置最多能放多少张全价票，g_i 表示在 f_i 最大时，后 i 个位置最多能放多少张半价票，h_i 表示在 f_i,g_i 均最大时，最多还能剩下多少个 i 开始的前缀空位。

转移有两种：

转移的时候，用一个 pre 数组记录一下方案即可知道方案。

代码

#include<bits/stdc++.h> 
#define int long long
#define N 1000005
#define pii pair<int,int>
#define x first
#define y second
#define mod 100000000000
#define pct __builtin_popcount
#define inf 2e9
using namespace std;
int T=1,n,l,q,a[N],f[N],g[N],h[N],pre[N];
bool st[N];
void solve(int cs){
    cin>>n>>l>>q;
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        if(!a[x])a[x]=i;
    }
    for(int i=n;i;i--){
        f[i]=0;
        if(i+l-1<=n&&a[i]){
            f[i]=f[i+l]+1;
            g[i]=g[i+l];
            h[i]=0;
            pre[i]=i+l;
        }
        int nf=f[i+1],ng=g[i+1]+(h[i+1]==l-1),nh=(h[i+1]+1)%l;
        if(nf>f[i]||(nf==f[i]&&ng>g[i])||(nf==f[i]&&ng==g[i]&&nh>h[i])){
            f[i]=nf;
            g[i]=ng;
            h[i]=nh;
            pre[i]=i+1;
        }
    }
    if(f[1]+g[1]>q){
        cout<<f[1]+q<<'\n'<<q<<'\n';
    }
    else{
        cout<<f[1]*2+g[1]<<'\n'<<f[1]+g[1]<<'\n';
    }
    int x=1;
    while(x<=n){
        if(pre[x]-x==l&&a[x]){
            st[a[x]]=1;//给全价票打上标记 
        }
        x=pre[x];
    }
    int las=1,nxt=1;//nxt是下一段的开头在哪 
    x=1;
    while(x<=n){
        while(st[las]&&las<=q)las++;
        if(pre[x]-x==l&&a[x]){//有全价票 
            cout<<a[x]<<' '<<x<<'\n';
            nxt=pre[x];
        }
        else if(x-nxt+1>=l&&las<=q){//已经可以再开一段，且没有全价票 
            cout<<las<<' '<<nxt<<'\n';
            st[las]=1;
            nxt=x+1;
        }
        x=pre[x];
    }
}
void solution(){
    /*
    nothing here
    */
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//  cin>>T;
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    return 0;
}