洛谷P3724 [AH2017/HNOI2017]大佬（决策单调性）
这个思路很妙诶->这里
以下为了方便，我把自信说成血量好了
虽然表面上看起来每一天有很多种选择，然而我们首先要保证的是不死，然后考虑不死的情况下最多能拿出多少天来进行其他操作。不死可以dp，最大伤害可以枚举
首先我们要保证不死。设$dp[i][j]$表示在第$i$天，血量为$j$时最多多少天不刷题，那么这个可以直接dp出来
我们设$D$为dp数组的最大值，即最多有多少天可以使用
在这$D$天里，我们只需要选3,4,5操作，剩下的就可以多退少补
我们假设两次怼大佬的情况分别为$(d1,f1),(d2,f2)$其中$d$表示需要花费几天，$f$表示能打掉多少血
那么$f1+f2<=HP$，否则大佬生命值就为负的了，还得满足$HP-f1-f2<=D-d1-d2$，也就是说剩下的血要能在剩余的天数内执行操作$1$打完
同理，如果怼一次的话就是$f1<=HP$且$HP-f1<=D-d1$，不怼的话就是$HP>=0,HP<=D$
那么我们可以用dfs+判重枚举出所有的$(d,f)$，然后以$f$为第一关键字，$d$为第二关键字排序，移项，发现要满足$D>=HP-f1+d1-f2+d2$，我们可以枚举$(f1,d1)$，然后发现这$f$是有单调性的，那么就可以弄一个指针在那里扫，然后记录一下满足$f2+f1<=HP$的最小的$-f2+d2$，那么可以O(状态数)通过此题
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #include<queue> 7 #define ll long long 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 char buf[1<<21],*p1=buf,*p2=buf; 11 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 12 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 13 inline int read(){ 14 #define num ch-'0' 15 char ch;bool flag=0;int res; 16 while(!isdigit(ch=getc())) 17 (ch=='-')&&(flag=true); 18 for(res=num;isdigit(ch=getc());res=res*10+num); 19 (flag)&&(res=-res); 20 #undef num 21 return res; 22 } 23 const int N=2100005,mod=3587201; 24 pair<int,int> Q[N]; 25 int n,m,mc,D,MAXC,tp,Maxsize; 26 int dp[105][105],a[105],w[105],C[105]; 27 struct ed{int step,F,L;}; 28 queue<ed> Que; 29 struct ED{ 30 int ver[N],Next[N],head[mod+5],edge[N],tot; 31 inline void insert(int u,int v){ 32 int tmp=((ll)u*100+v)%mod; 33 ver[++tot]=u,Next[tot]=head[tmp],head[tmp]=tot,edge[tot]=v; 34 } 35 inline bool query(int u,int v){ 36 int tmp=((ll)u*100+v)%mod; 37 for(int i=head[tmp];i;i=Next[i]) 38 if(u==ver[i]&&v==edge[i]) return true; 39 return false; 40 } 41 }map; 42 //手写map，hash判重 43 void init(){ 44 for(int i=1;i<=n;++i) 45 for(int j=a[i];j<=mc;++j){ 46 cmax(dp[i][j-a[i]],dp[i-1][j]+1); 47 int tmp=min(mc,j-a[i]+w[i]); 48 cmax(dp[i][tmp],dp[i-1][j]); 49 } 50 for(int i=1;i<=n;++i) 51 for(int j=0;j<=mc;++j) 52 cmax(D,dp[i][j]); 53 } 54 void bfs(){ 55 Que.push((ed){1,1,0});//初始状态：使用一天，打出1伤害，等级0。 56 while(!Que.empty()){ 57 ed now=Que.front();Que.pop(); 58 if(now.step<D){ 59 Que.push((ed){now.step+1,now.F,now.L+1});//加1等级 60 if(now.L>1&&(ll)now.F*now.L<=(ll)MAXC&&!map.query(now.F*now.L,now.step+1)){ 61 //注意加longlong防止爆int，但哈希炸了也没事 62 //下面不用加longlong是因为MAXC在int范围内，如果小于肯定没超 63 ed tmp=(ed){now.step+1,now.F*now.L,now.L}; 64 Que.push(tmp); 65 Q[++tp]=make_pair(tmp.F,tmp.step); 66 //此处才加入队列，不能直接从Que取出来就加入，因为只加等级的状态是不优的，只有乘了，才更好。 67 map.insert(tmp.F,tmp.step); 68 } 69 } 70 } 71 } 72 int main(){ 73 //freopen("testdata.in","r",stdin); 74 n=read(),m=read(),mc=read(); 75 for(int i=1;i<=n;++i) a[i]=read(); 76 for(int i=1;i<=n;++i) w[i]=read(); 77 for(int i=1;i<=m;++i) C[i]=read(),cmax(MAXC,C[i]); 78 init(),bfs(); 79 sort(Q+1,Q+1+tp); 80 for(int i=1;i<=m;++i){ 81 if(C[i]<=D){puts("1");continue;}//按照单调性找是否有解。 82 int flag=0,mn=0x3f3f3f3f; 83 for(int j=tp,k=1;j;--j){ 84 while(k<tp&&Q[k].first+Q[j].first<=C[i]) cmin(mn,Q[k].second-Q[k].first),++k; 85 if(mn-Q[j].first+Q[j].second+C[i]<=D){flag=1;break;} 86 if(Q[j].first<=C[i]&&C[i]-Q[j].first+Q[j].second<=D){flag=1;break;} 87 } 88 printf("%d ",flag); 89 } 90 return 0; 91 }