# 洛谷3724 [ah2017_hnoi2017]大佬

## 一首凉凉送给自己

Posted by yjjr's blog on March 6, 2018

# 题目

## 题目描述

还一句嘴，大佬会有点惊讶，导致大佬的自信值 C 减小 1。



## 输入输出样例

### 输入样例#1

30 20 30
15 5 24 14 13 4 14 21 3 16 7 4 7 8 13 19 16 5 6 13 21 12 7 9 4 15 20 4 13 12
22 21 15 16 17 1 21 19 11 8 3 28 7 10 19 3 27 17 28 3 26 4 22 28 15 5 26 9 5 26
30
10
18
29
18
29
3
12
28
11
28
6 1 6
27
27
18
11
26
1


### 输出样例#1

0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1


## 说明

20%数据保证: 1≤n≤10。

100%数据保证: 1 ≤ n,mc ≤ 100; 1≤m≤20; 1≤a[i],w[i]≤mc; 1≤C[i] ≤10^8

# 分析

f1,d1是枚举的，那么自然-f1+d2最小即可

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=106,mod=1125527;
int n,m,mc,mxd,mx,top,f[maxn][maxn],a[maxn],w[maxn],c[maxn];
pair<int,int>que[1000006];
struct ed{int step,F,L;};
queue<ed>Que;
struct map{
struct edge{int x,y,next;}e[1000006];
int cnt,last[mod+6];
void insert(int x,int y){
int tmp=((ll)x*106+y)%mod;
e[++cnt]=(edge){x,y,last[tmp]};last[tmp]=cnt;
}
bool query(int x,int y){
int tmp=((ll)x*106+y)%mod;
reg(tmp)if(x==e[i].x&&y==e[i].y)return 1;
return 0;
}
}mp;
void bfs(){
Que.push((ed){1,1,0});
while(!Que.empty()){
ed now=Que.front();Que.pop();
if(now.step<mxd){
Que.push((ed){now.step+1,now.F,now.L+1});
if(now.L>1&&(ll)now.F*now.L<=(ll)mx&&!mp.query(now.F*now.L,now.step+1)){
ed tmp=(ed){now.step+1,now.F*now.L,now.L};
Que.push(tmp);
que[++top]=(pair<int,int>){tmp.F,tmp.step};
mp.insert(tmp.F,tmp.step);
}
}
}
}
int main()
{
rep(i,1,n)
rep(j,a[i],mc){
f[i][j-a[i]]=max(f[i][j-a[i]],f[i-1][j]+1);
int tmp=min(mc,j-a[i]+w[i]);
f[i][tmp]=max(f[i][tmp],f[i-1][j]);
}
rep(i,1,n)
rep(j,0,mc)mxd=max(mxd,f[i][j]);
bfs();
sort(que+1,que+1+top);
rep(i,1,m){
if(c[i]<=mxd){puts("1");continue;}
int flag=0,mn=inf;
for(int j=top,k=1;j;j--){
while(k<top&&que[k].first+que[j].first<=c[i])mn=min(mn,que[k].second-que[k].first),k++;
if(mn+que[j].second-que[j].first+c[i]<=mxd){flag=1;break;}
if(que[j].first<=c[i]&&c[i]-que[j].first+que[j].second<=mxd){flag=1;break;}
}
printf("%d\n",flag);
}
return 0;
}