【cf1012f】Passports

Source

cf1012f
我的阅读理解好差啊,看错了3次题,无限自闭
题意:
有pp=1/2个护照,然后要按顺序去n个国家旅游
给定时间区间(开始st,长度ln,办签证时间ti),保证区间不相交
每个签证必须在非旅游时间开始办理,在经过ti个晚上后送到家中
如果去某个国家x用的是A护照,则此时A护照必须在非办理状态,而且上面有x的签证
求可行方案,形式为每个签证在哪个护照上、开始办理时间

Hint

请先思考后再展开

f[S]表示处理了这个集合的签证的最短时间
那么你需要保证,每个签证都在对应国家前得到,而且办签证期间不能使用这个护照旅游

Solution

请先思考后再展开

这个dp需要达到 $n2^n$ 的复杂度
建议先写个暴力,然后逐步优化
例如是具有单调性的:无论是j2<=i还是最小化f,都应该选择最小的合法j2,而且j2的移动在按ti排序后是单调的

先考虑pp=1,办签证的时间和旅游不能重叠,直接判 $f[2^n-1]$
然后pp=2,判 $f[a]和f[2^n-1-a]$ 即可

然后我代码有个小小的lower_bound,是可以去掉保证复杂度的,懒得搞了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(ll &x,const int y) {x=x<y?x:y;}
const int MAX_N=24;
const ll MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int bin[40],mxb[1<<MAX_N];
struct City
{
int st,ed,ti,id;
friend bool operator < (City a,City b) {return a.st<b.st;}
}p[MAX_N];int p2[MAX_N];
bool cmp(int a,int b) {return p[a].ti<p[b].ti;}
int n,pp;
int f[1<<MAX_N];pr ans[MAX_N];
struct FF{int from,time,nxt;}fm[1<<MAX_N];
bool check(int now,int op)
{
if(f[now]==f[bin[n]]) return 0;
while(now>0)
{
int from=fm[now].from;
if(from==0) return 0;
ans[p[from].id]=MP(op,fm[now].time);
now^=bin[from-1];
}
return 1;
}
int pre[MAX_N][MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
for(int i=1;i<bin[MAX_N];i++) mxb[i]=max(mxb[i>>1]+1,(i&1)?1:0);
for(int l=0;l<MAX_N;l++) for(int r=l;r<MAX_N;r++) pre[l][r]=(bin[r+1]-1)^(bin[l]-1);
n=qread(),pp=qread();
for(int i=1;i<=n;i++) p[i].st=qread(),p[i].ed=p[i].st+qread()-1,p[i].ti=qread(),p[i].id=i;
sort(p+1,p+n+1);p[n+1].st=INF*2;
for(int i=1;i<=n;i++) p2[i]=i;sort(p2+1,p2+n+1,cmp);
memset(f,127,sizeof f);f[0]=1;
for(int S=0;S<bin[n];S++)
{
int nxt=upper_bound(p+1,p+n+1,(City){f[S],0,0,0})-p;
int j=nxt-(f[S]<=p[nxt-1].ed),j2=j;
for(int i=1;i<=n;i++) if(!(S&bin[p2[i]-1]))
{
int S2=S|bin[p2[i]-1];
if(f[S]>p[nxt-1].ed)
{
int time=f[S]+p[p2[i]].ti,j2=upper_bound(p+1,p+n+1,(City){time,0,0,0})-p;
bool bk=(j2<=p2[i]);if(nxt<=j2-1) bk&=(S2&pre[max(nxt-1,0)][max(j2-2,0)])==0;
if(bk and time<f[S2]) {f[S2]=time,fm[S2]=(FF){p2[i],f[S]};continue;}
}
j=nxt-(f[S]<=p[nxt-1].ed),j2=j;
for(;j<n;j++) if(p[j].ed+1!=p[j+1].st)//debug
{
int time=(p[j].ed+1)+p[p2[i]].ti;while(p[j2].st<=time) j2++;
bool bk=1;if(j+1<=j2-1) bk&=(S2&pre[j][max(j2-2,0)])==0;
if(bk)
{
if(time<f[S2] and j2<=p2[i]) f[S2]=time,fm[S2]=(FF){p2[i],p[j].ed+1};
break;
}
}
}
}
if(pp==1)
{
if(!check(bin[n]-1,1)) puts("NO");
else
{
for(int i=1;i<=n;i++) if(ans[i].FR==0) {puts("NO");return;}
puts("YES");for(int i=1;i<=n;i++) printf("%d %d\n",ans[i].FR,ans[i].SE);
}
}
else
{
for(int a=0;a<bin[n];a++) if(check(a,1) and check((bin[n]-1)^a,2))
{
for(int i=1;i<=n;i++) if(ans[i].FR==0) {puts("NO");return;}
puts("YES");for(int i=1;i<=n;i++) printf("%d %d\n",ans[i].FR,ans[i].SE);return;
}
puts("NO");
}
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8470.html
转载请注明出处,谢谢!