LibreOJ 2021 「AHOI / HNOI2017」大佬

注意到「不失败」和「打大佬」是相互独立的，考虑先用一个简单 DP 求出不失败的情况下最多可以留出多少天来打大佬。

然后考虑 BFS 出所有可能的 F 值和达到它的天数的状态。
注意天数不同的方案要保留，因为也会有贡献。

然后把 F 值排序，用双指针优化一下判定过程。

代码：

#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <tr1/unordered_set>
#include <tr1/unordered_map>
using namespace std;
const int N = 100;
const int M = 20;
const int LEN = 1e6;
int n,m,mc;
int a[N + 5],w[N + 5],C[M + 5],lim;
int f[N + 5][N + 5],D;
tr1::unordered_map< int,tr1::unordered_set<int> > vis;
struct note
{
    int l,d;
    int f;
} q[LEN * 10 + 5];
int head,tail,tot;
pair<int,int> d[LEN + 5];
void bfs()
{
    q[++tail] = (note){0,1,1},vis[1].insert(1),d[++tot] = make_pair(1,1);
    for(register note p;head < tail;)
    {
        p = q[++head];
        if(p.d < D)
        {
            q[++tail] = (note){p.l + 1,p.d + 1,p.f};
            if(p.l > 1 && (long long)p.f * p.l <= lim && (!vis.count(p.f * p.l) || !vis[p.f * p.l].count(p.d + 1)))
                q[++tail] = (note){p.l,p.d + 1,p.f * p.l},vis[p.f * p.l].insert(p.d + 1),d[++tot] = make_pair(p.f * p.l,p.d + 1);
        }
    }
}
inline bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.first == b.first;
}
int main()
{
    scanf("%d%d%d",&n,&m,&mc);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    for(register int i = 1;i <= n;++i)
        scanf("%d",w + i);
    for(register int i = 1;i <= m;++i)
        scanf("%d",C + i),lim = max(lim,C[i]);
    memset(f,0x3f,sizeof f),f[0][mc] = 0;
    for(register int i = 1;i <= n;++i)
        for(register int j = a[i];j <= mc;++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),
            f[i][j - a[i]] = min(f[i][j - a[i]],f[i - 1][j]);
    for(register int i = 1;i <= n;++i)
        for(register int j = 0;j <= mc;++j)
            D = max(D,i - f[i][j]);
    bfs(),sort(d + 1,d + tot + 1),tot = unique(d + 1,d + tot + 1,cmp) - d - 1;
    for(register int i = 1,flag;i <= m;++i)
    {
        if(C[i] <= D)
        {
            puts("1");
            continue;
        }
        flag = 0;
        int p1 = 1,p2 = 1,mx = -0x3f3f3f3f;
        for(;p1 <= tot && d[p1].first <= C[i];++p1)
            if(d[p1].first + D - d[p1].second >= C[i])
            {
                flag = 1;
                break;
            }
        --p1;
        if(flag)
        {
            puts("1");
            continue;
        }
        for(;p1;--p1)
        {
            for(;p2 <= tot && d[p1].first + d[p2].first <= C[i];++p2)
                mx = max(mx,d[p2].first - d[p2].second);
            if(d[p1].first - d[p1].second + mx + D >= C[i])
            {
                flag = 1;
                break;
            }
        }
        putchar(flag ^ '0'),puts("");
    }
}