Link：点我点我:-)
Description：
人们总是难免会碰到大佬。他们趾高气昂地谈论凡人不能理解的算法和数据结构，走到任何一个地方，大佬的气场就能让周围的人吓得瑟瑟发抖，不敢言语。 你作为一个 OIER，面对这样的事情非常不开心，于是发表了对大佬不敬的言论。 大佬便对你开始了报复，你也不示弱，扬言要打倒大佬。
现在给你讲解一下什么是大佬，大佬除了是神犇以外，还有着强大的自信心，自信程度可以被量化为一个正整数 C（ 1<=C<=10^8）， 想要打倒一个大佬的唯一方法是摧毁 Ta 的自信心，也就是让大佬的自信值等于 0（恰好等于 0，不能小于 0）。 由于你被大佬盯上了，所以你需要准备好 n(1<=n<=100)天来和大佬较量，因为这 n 天大佬只会嘲讽你动摇你的自信，到了第n+1 天，如果大佬发现你还不服，就会直接虐到你服，这样你就丧失斗争的能力了。
你的自信程度同样也可以被量化，我们用 mc (1 <= mc <= 100)来表示你的自信值上限。
在第 i 天（ i>=1），大佬会对你发动一次嘲讽，使你的自信值减小 a[i]，如果这个时刻你的自信值小于 0 了，那么你就丧失斗争能力，也就失败了（特别注意你的自信值为 0 的时候还可以继续和大佬斗争）。 在这一天， 大佬对你发动嘲讽之后，如果你的自信值仍大于等于 0，你能且仅能选择如下的行为之一：
１．还一句嘴，大佬会有点惊讶，导致大佬的自信值 C 减小 1。
２．做一天的水题，使得自己的当前自信值增加 w[i], 并将新自信值和自信值上限 mc 比较，若新自信值大于 mc，则新自信值更新为 mc。例如， mc=50， 当前自信值为 40， 若w[i]=5，则新自信值为 45，若 w[i]=11，则新自信值为 50。
３．让自己的等级值 L 加 1。
４．让自己的讽刺能力 F 乘以自己当前等级 L，使讽刺能力 F 更新为 F*L。
５．怼大佬，让大佬的自信值 C 减小 F。并在怼完大佬之后，你自己的等级 L 自动降为 0，讽刺能力 F 降为 1。由于怼大佬比较掉人品，所以这个操作只能做不超过 2 次。 特别注意的是，在任何时候，你不能让大佬的自信值为负，因为自信值为负，对大佬来说意味着屈辱，而大佬但凡遇到屈辱就会进化为更厉害的大佬直接虐飞你。在第 1 天，在你被攻击之前，你的自信是满的（初始自信值等于自信值上限 mc）， 你的讽刺能力 F 是 1， 等级是 0。
现在由于你得罪了大佬，你需要准备和大佬正面杠，你知道世界上一共有 m（ 1<=m<= 20）个大佬，他们的嘲讽时间都是 n 天，而且第 i 天的嘲讽值都是 a[i]。不管和哪个大佬较量，你在第 i 天做水题的自信回涨都是 w[i]。 这 m 个大佬中只会有一个来和你较量（ n 天里都是这个大佬和你较量），但是作为你，你需要知道对于任意一个大佬，你是否能摧毁他的自信，也就是让他的自信值恰好等于 0。和某一个大佬较量时，其他大佬不会插手。
Inut：
第一行三个正整数 n,m,mc。分别表示有 n 天和 m 个大佬, 你的自信上限为 mc。
接下来一行是用空格隔开的 n 个数，其中第 i(1<=i<=n)个表示 a[i]。
接下来一行是用空格隔开的 n 个数，其中第 i(1<=i<=n)个表示 w[i]。
接下来 m 行，每行一个正整数，其中第 k(1<=k<=m)行的正整数 C[k]表示第 k 个大佬的初始自信值。
Output：
共 m 行，如果能战胜第 k 个大佬（让他的自信值恰好等于 0），那么第 k 行输出 1，否则输出 0。
Hint：
20%数据保证: 1≤n≤10。 另有 20%数据保证:1 ≤ C[i],n,mc ≤ 30。 100%数据保证: 1 ≤ n,mc ≤ 100; 1≤m≤20; 1≤a[i],w[i]≤mc; 1≤C[i] ≤$10^8$
Analysis：
1. 首先是一个简单的预处理DP，需要求出一个数D，表示的是最多可以拥有的自由天数(不给自己加信心)，具体可见程序
2. 再用一个Bfs求出若干对二元组(F, day)，表示可以在day干掉一个大佬。注意在Bfs中我们的day不用超过D，所以状态不是很多(不是特别清楚严谨的证明，但是的确不多)，但是这里要用一个STL的map的嵌套(就是二维都是map)记录状态，否则空间还是很危险
3. 那么怼大佬两次就是拼凑两个二元组，为了不落下一次怼的情况，我们再加入(0, 0)二元组。
4. 对于(f1, d1), (f2, d2)这两个二元组可以怼死一个信心值为C的大佬，当且仅当：C-f1-f2 <= D-d1-d2，且f1+f2 <= C，移项可得:C-D <= (f1-d1)+(f2-d2) () 那么把二元组按F排序，从大到小枚举第一个二元组，第二个二元组是单调队列从小到大，每次把可以满足条件的第二个二元组往后枚，过程中记录(f2-d2)的最大值，然后如果在某个时刻不等式()满足了就可以判断成功
Some things：
预处理还是容易想出来的，然而我认为状态数的问题比较玄学，每次会有两个决策，而在极限数据下可以使得D=100，应该是因为重复状态较多，所以实测在bzoj可以通过(洛谷需手动开优化)。如果C的最大值为$10^8$并且使D=100，下方程序是不可以过上述设计的数据的 然而去看了一下另一位大佬的代码，跑的很快。非常巧妙，他使用了一个$10^8$的char数组用来记录每个数是否可以在D步中出现(这个给好评)，具体实现则是使用Dfs，然而速度惊人的快。如果D=100，可以产生的数字只有853780个。后面直接可以平方判断，并且出奇快。我会在我的代码之后附上那位大佬的代码。
Thought:
考场上把前面那一个最简单的预处理写了出来。然后开始使用dfs一顿乱搜，并没有记忆化，一是感觉这题是数学推导，而是感觉状态数太多。
那么要汲取经验，对于搜索题，可以尝试记忆化，实在不行可以用map。搜索题的状态往往没有所估计的那么多，并且记忆化可以带来很好的优化。
有时候觉得搜索并不是正解，但是经过好的优化的它往往可以带来惊喜，人要有梦想！
Code：
Mine
//miaomiao 5.1 dalao
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define N (100+5)
#define ZT (4000000+5)
char chr;
inline void Read(int &x){
chr = getchar();
while(chr < '0' || chr > '9') chr = getchar();
x = 0;
while(chr >= '0' && chr <= '9'){
x = (x<<1)+(x<<3)+(chr^'0');
chr = getchar();
}
}
struct node{
int nF, Day;
bool operator <(const node &rhs)const{
return nF < rhs.nF;
}
}Pair[ZT];
int n, m, mc, D, an, pn, f[N][N], a[N], w[N], dalao[N];
int F[ZT], L[ZT], Da[ZT], MXV;
map<int, map<int, int> > d;
inline void Bfs(){
int st = 0, en = 1;
d[F[en]=1][L[en]=0] = Da[1] = 1;
while(st < en){
++st;
if(Da[st] > D) break;
if(1ll*(L[st]+1)*F[st] <= 1ll*MXV && !d[F[st]][L[st]+1]){
Da[++en] = d[F[st]][L[st]+1] = d[F[st]][L[st]]+1;
F[en] = F[st]; L[en] = L[st]+1;
}
if(L[st]>1 && 1ll*L[st]*F[st] <= 1ll*MXV && !d[F[st]*L[st]][L[st]]){
Da[++en] = d[F[st]*L[st]][L[st]] = d[F[st]][L[st]]+1;
F[en] = F[st]*L[st]; L[en] = L[st];
}
}
Pair[++pn] = (node){0, 0};
For(i, 1, en)
Pair[++pn] = (node){F[i], Da[i]};
}
void Init(){
Set(f, -1); f[0][0] = mc;
For(i, 1, n) For(j, 0, i){
f[i][j] = max(f[i][j], f[i-1][j]-a[i]);
if(j && f[i-1][j-1] >= a[i])
f[i][j] = max(f[i][j], min(f[i-1][j-1]-a[i]+w[i], mc));
if(f[i][j] >= 0) D = max(D, i-j);
}
Bfs(); sort(Pair+1, Pair+pn+1);
}
inline void Solve(){
int C, f1, d1, v2, j;
bool found;
For(di, 1, m){
C = dalao[di]; j = 1; v2 = 0; found = false;
Forr(i, pn, 1){
f1 = Pair[i].nF, d1 = Pair[i].Day;
if(f1 > C) continue;
while(j<i && Pair[j].nF+f1 <= C) v2 = max(v2, Pair[j].nF-Pair[j].Day), ++j;
if(C-D <= f1-d1+v2){
found = true; break;
}
}
printf("%c\n", found? '1': '0');
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
Read(n); Read(m); Read(mc);
For(i, 1, n) Read(a[i]);
For(i, 1, n) Read(w[i]);
For(i, 1, m) Read(dalao[i]), MXV = max(MXV, dalao[i]);
Init(); Solve();
return 0;
}
Dfs版本
#include <bits/stdc++.h>
using namespace std;
const int N=105,M=100000005,K=1000005;
int n,m,l,w,mc,a[N],b[N],c[K],f[N][N];
char s[M];
void dfs1(int i,int f,int c)
{
if(i>l)return ;
dfs1(i+1,f,c+1);
if(c&&f<M/c)
if(!s[f*c]||i<s[f*c])
s[f*c]=i,dfs1(i+1,f*c,c);
}
int main()
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
scanf("%d%d%d",&n,&m,&mc);
int i,j,p;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
f[0][mc]=1;
for(i=0;i<n;i++)
for(j=a[i+1];j<=mc;j++)
if(f[i][j])
{
f[i+1][j-a[i+1]]=max(f[i+1][j-a[i+1]],f[i][j]+1);
f[i+1][min(mc,j-a[i+1]+b[i+1])]=max(f[i+1][min(mc,j-a[i+1]+b[i+1])],f[i][j]);
}
for(i=0;i<=n;i++)
for(j=0;j<=mc;j++)
l=max(l,f[i][j]-1);
// l = 100;
dfs1(1,1,0);
for(i=1;i<M;i++)
if(s[i])
c[++c[0]]=i;
// printf("c[0] = %d\n", c[0]);
while(m--)
{
scanf("%d",&w);
p=0;
for(j=1;j<=c[0]&&c[j]<=w&&!p;j++)
if(w-c[j]+s[c[j]]+1<=l)
p=1;
for(i=0;i<=l&&!p;i++)
for(j=1;j<=c[0]&&i+c[j]<=w&&!p;j++)
if(s[w-c[j]-i]&&i+s[c[j]]+s[w-c[j]-i]+2<=l)
p=1;
printf("%d\n",p);
}
return 0;
}