是乱搞，，

Solution

首先可以发现你可以把空闲的最多操作数求出来

其次你可以发现一次怼人能得到的状态数有限

那么把所有状态爆搞出来

之后再强行枚举一发就能直接过掉这题了，，，

事实上算出来的最坏复杂度是 1.7e9，但是呢加了一些剪枝，所以大概也算能接受...？

Code

// Code by ajcxsu
// Problem: dalao

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;
using namespace __gnu_pbds;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }

typedef long long ll;
gp_hash_table<ll, int> s[110];
int gat=0;
int rt=101;
void dfs(ll f, int l, int k) {
    if(f*l>100000000ll) return;
    if(k+1>gat) return;
    if(f*l<=100000000ll && (s[l].find(f*l)==s[l].end() || s[l][f*l]>k+1)) s[l][f*l]=k+1, dfs(f*l, l, k+1);
    dfs(f, l+1, k+1);
}

const int N=210, M=8.6e5;
int f[N][N], a[N], w[N], c[N];
struct Thing { int v, w; } t[M];
bool cmp(const Thing &a, const Thing &b) { return a.v<b.v; }
bool ans[N];

int main() {    
    int n, m, mc;
    gn(n, m, mc);
    for(int i=1;i<=n;i++) gn(a[i]);
    for(int i=1;i<=n;i++) gn(w[i]);
    for(int i=0;i<m;i++) gn(c[i]);
    CLR(f, 0x3f);
    f[0][mc]=0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=2*mc;j++) {
            if(j+a[i]<=2*mc) f[i][j]=f[i-1][j+a[i]];
            if(j+a[i]-w[i]<=2*mc && j-w[i]>=0) f[i][j]=min(f[i][j], f[i-1][j+a[i]-w[i]]+1);
            gat=max(gat, i-f[i][j]);
            if(j>mc) f[i][mc]=min(f[i][j], f[i][mc]), f[i][j]=0x3f3f3f3f;
        }
    }
    dfs(1, 0, 0);
    int p=0;
    for(int i=0;i<=100;i++)
        for(auto it:s[i]) if(s[rt].find(it.first)==s[rt].end() || s[rt][it.first]>it.second) s[rt][it.first]=it.second;
    for(auto it:s[rt]) t[p++]={it.first, it.second};
    sort(t, t+p, cmp);
    for(int i=0;i<m;i++)
        for(int nc=0;nc<=gat;nc++) {
            if(c[i]-nc==0) ans[i]=1;
            if(s[rt].find(c[i]-nc)!=s[rt].end() && s[rt][c[i]-nc]+nc+1<=gat) ans[i]=1;
            for(int j=0;j<p && t[j].v<c[i]-nc && !ans[i];j++)
                if(s[rt].find(c[i]-nc-t[j].v)!=s[rt].end() && s[rt][c[i]-nc-t[j].v]+nc+t[j].w+2<=gat)
                    ans[i]=1;
        }
    for(int i=0;i<m;i++) printf("%d\n", ans[i]);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-hnoi-2017-dalao.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆