大佬[AHOI2017/HNOI2017][搜索][Dp][综合]

题目

Luogu

并且生命上限为 $mc$ ，最多怼大佬两次

思路

思路倒是都想到了,但是实现…
首先发现我死不死和大佬死不死是两个步骤
$f_{i,j}$ 前 $i$ 个选 $j$ 个最大生命然后可以处理出剩余天数
然后由于 $(f,t)$ 二元组比较小，考虑爆搜
但是要注意存储什么，如果 $(f,t,l)$ 都存会多出许多无用状态，并且 $(f,t)$ 当 $t$ 较大时可能后面有用（$level$ 比较大）
考虑更新时候优先扩大 $l$ 再扩大 $f$
然后考虑怼两次 $f_i+f_j\le C\le f_i+f_j+d?t_i?t_j$
然后处理前缀最小值即可

#include<set> 
#include<map> 
#include<stack> 
#include<ctime> 
#include<cstdio> 
#include<queue> 
#include<cmath> 
#include<vector> 
#include<ctime> 
#include<cstring> 
#include<climits> 
#include<iostream> 
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9'){
    x=x*10+c-'0';c=getchar();}return f*x;
}
#define mp make_pair
const int MAXN=100;
const int INF=0x3f3f3f3f;
LL f[MAXN+5][MAXN+5];
const int MOD=10007;
vector<pair<int,int> > P,Hash[MOD];
bool Insert(int d,pair<int,int> tmp){
    int u=tmp.first%MOD;for(int i=0;i<(int)Hash[u].size();i++)if(Hash[u][i].first==tmp.first){
    bool t=0;if(Hash[u][i].second>tmp.second)t=1;Hash[u][i].second=min(Hash[u][i].second,tmp.second);return t;}Hash[u].push_back(tmp);return 1;
}
struct node{
    int f,l,t;};
int d,MaxC,a[MAXN+5],w[MAXN+5],C[MAXN+5];
void BFS(){
    queue<node> Q;Q.push((node){
    1,0,1});Insert(1,mp(1,1));while(!Q.empty()){
    node u=Q.front();Q.pop();if(u.t>=d) continue;Q.push((node){
    u.f,u.l+1,u.t+1});if(u.l>1&&1ll*u.f*u.l<=MaxC&&Insert(u.t+1,mp(u.f*u.l,u.t+1)))Q.push((node){
    u.f*u.l,u.l,u.t+1});}return ;
}
int main(){
    //f[i][j]:?°i????j?????ü????×??ó?ú?ü int n=read(),m=read(),mc=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++)w[i]=read();for(int i=1;i<=m;i++)C[i]=read(),MaxC=max(MaxC,C[i]);memset(f,-0x3f,sizeof(f));f[0][0]=mc;for(int i=1;i<=n;i++){
    for(int j=0;j<=i;j++){
    if(f[i-1][j]-a[i]>=0)f[i][j]=f[i-1][j]-a[i];if(j&&f[i-1][j-1]-a[i]>=0)f[i][j]=max(f[i][j],min(f[i-1][j-1]+w[i]-a[i],1ll*mc));if(f[i][j]>=0)d=max(d,i-j);}}BFS();int tp=0;for(int o=0;o<=100;o++)for(int i=0;i<MOD;i++)for(int j=0;j<(int)Hash[o][i].size();j++)tp++,P.push_back(Hash[o][i][j]);sort(P.begin(),P.end());//printf("%d\n",tp);for(int i=1;i<=m;i++){
    if(C[i]<=d){
    puts("1");continue;}int Max=-INF;for(int j=0;j<tp;j++)if(P[j].first<=C[i]&&C[i]<=P[j].first+d-P[j].second){
    puts("1");goto Break;}for(int R=tp-1,L=-1;R>=L;R--){
    while(L+1<R&&P[L+1].first+P[R].first<=C[i])L++,Max=max(Max,P[L].first-P[L].second);if(C[i]-d-(P[R].first-P[R].second)<=Max){
    puts("1");goto Break;}}puts("0");Break:;}return 0;
}