自动搬运

查看原文

来自洛谷，原作者为

	zxh923 这个奶龙在APIO T3中以为解法是假的并写到了特殊性质的特判里，望周知

搬运于2025-08-24 22:32:13，当前版本为作者最后更新于2024-10-12 16:36:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P7688 [CEOI2005] Ticket Office 题解

题目传送门。

思路

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

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

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

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

转移有两种：

• 当这个位置有全价票可以放置时，有转移 $f_i\leftarrow f_{i+l}+1,g_i\leftarrow g_{i+l},h_{i}\leftarrow 0$。

• 对于所有情况，有转移 $f_i\leftarrow f_{i+1},g_i\leftarrow g_{i+1}+[h_{i+1}=l-1],h_{i}\leftarrow (h_{i+1}+1)\bmod l$。

转移的时候，用一个 $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;
}