LOJ #2021. 「AHOI / HNOI2017」大佬 BFS+Hash+动态规划

嘴巴上把这道题切了，但是写代码的时候好多细节都需要注意.  

1. 大概可以猜到能表示出的数字比多，但是这一步要用 BFS+hash 才行，因为用 DP 求解的话会有好多无用状态. 

2. 做动态规划的时候如果对与状态有限制条件的话比较好写的方法是由合法状态去转移下一步，而不是枚举当前状态去找上一步的状态.

3. 到了最后一步，知道肯定有单调性，但是发现有两个维度的限制，需要再加一个 log，那么这个时候就要认真观察一下式子，可能发现如果满足一个，另一个就无用了. 

code: 

#include <cstdio>
#include <cstring> 
#include <map>    
#include <queue> 
#include <set>    
#include <cstdlib> 
#include <ctime>
#include <algorithm>    
#define N 204  
#define M 2000006  
#define ll long long     
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;     
const int mod=1000007;  
const int MAX=100000000;   
int n,m,mc,day,tot,cnt;       
int a[N],w[N],f[N][N],c[N];                                         
struct Hash
{        
    int hd[M],X[M<<2],Y[M<<2],nex[M<<2],edges; 
    void Add(int x,int y)
    {
        int pos=(1ll*x*101+y)%mod;
        nex[++edges]=hd[pos],hd[pos]=edges,X[edges]=x,Y[edges]=y;                     
    }
    int query(int x,int y)
    {
        int pos=(1ll*x*101+y)%mod;
        for(int i=hd[pos];i;i=nex[i])
            if(X[i]==x&&Y[i]==y)return 1;
        return 0;
    }
}mp;                 
struct node 
{
    int step,x,y;   
    node(int step=0,int x=0,int y=0):step(step),x(x),y(y){}  
}ar[4000000],br[400000];     
bool cmp(node a,node b) 
{
    return a.x==b.x?a.step<b.step:a.x<b.x;   
} 
bool cmp2(node a,node b) 
{
    return a.step<b.step; 
}
queue<node>q;          
void init() 
{   
    q.push(node(1,1,0));  
    mp.Add(1,0);         
    ar[++tot]=node(1,1,0);     
    while(!q.empty())     
    {
        node e=q.front(); q.pop();     
        int x=e.x,y=e.y,step=e.step;           
        if(step>=day)  continue;     
        if(1ll*x*(y+1)<=MAX&&!mp.query(x,y+1))
        {
            mp.Add(x,y+1);                     
            q.push(node(step+1,x,y+1));  
        } 
        if(y>1&&1ll*x*y<=1ll*MAX&&!mp.query(1ll*x*y,y))   
        {
            mp.Add(x*y,y);       
            q.push(node(step+1,x*y,y));    
            ar[++tot]=node(step+1,x*y,0);   
        }               
    }
    sort(ar+1,ar+1+tot,cmp);   
    for(int i=1,j;i<=tot;i=j) 
    {      
        br[++cnt]=node(ar[i].step,ar[i].x,ar[i].y);    
        for(j=i;ar[j].x==ar[i].x;++j);   
    }             
}            
int main() 
{    
    // setIO("input");           
    int n,m,mc;   
    scanf("%d%d%d",&n,&m,&mc);       
    for(int i=1;i<=n;++i)  
        scanf("%d",&a[i]);  
    for(int i=1;i<=n;++i) 
        scanf("%d",&w[i]);  
    for(int i=1;i<=m;++i) 
        scanf("%d",&c[i]); 
    memset(f,0x3f,sizeof(f));              
    f[0][mc]=0;      
    for(int i=1;i<=n;++i) 
    {
        for(int j=a[i];j<=mc;++j) 
        {
            f[i][j-a[i]]=min(f[i][j-a[i]],f[i-1][j]);    
            f[i][min(j-a[i]+w[i],mc)]=min(f[i][min(j-a[i]+w[i],mc)],f[i-1][j]+1); 
        }
    }            
    for(int i=1;i<=n;++i) for(int j=0;j<=mc;++j) day=max(day,i-f[i][j]);    
    init();                      
    for(int i=1;i<=m;++i) 
    { 
        int flag=0; 
        for(int j=1;j<=cnt;++j) 
        {
            if(br[j].x+day-br[j].step>=c[i]&&br[j].step<=day&&br[j].x<=c[i]) 
            {    
                flag=1; 
                break; 
            } 
        }
        if(flag) printf("%dn",1); 
        else  
        { 
            int maxc=-1000000000;  
            for(int k=cnt,j=1;k>=1;--k) 
            {
                for(;j<=cnt&&br[j].x+br[k].x<=c[i];++j) 
                    maxc=max(maxc,br[j].x-br[j].step);          
                if(maxc+br[k].x-br[k].step>=c[i]-day) {  flag=1; break; } 
            } 
            printf("%dn",flag);  
        }
    }
    return 0; 
}