【BZOJ4828】【HNOI2017】大佬（動态規劃）

題面

BZOJ

洛谷

LOJ

人們總是難免會碰到大佬。他們趾高氣昂地談論凡人不能了解的算法和資料結構，走到任何一個地方，大佬的氣場

就能讓周圍的人吓得瑟瑟發抖，不敢言語。你作為一個OIER，面對這樣的事情非常不開心，于是發表了對大佬不敬

的言論。大佬便對你開始了報複，你也不示弱，揚言要打倒大佬。現在給你講解一下什麼是大佬，大佬除了是神犇

以外，還有着強大的自信心，自信程度可以被量化為一個正整數 C（1<=C<=10^8），想要打倒一個大佬的唯一方法

是摧毀 Ta的自信心，也就是讓大佬的自信值等于 0（恰好等于 0，不能小于 0 ）。由于你被大佬盯上了，是以你

需要準備好 n(1<=n<=100)天來和大佬較量，因為這 n天大佬隻會嘲諷你動搖你的自信，到了第n+1天，如果大佬發

現你還不服，就會直接虐到你服，這樣你就喪失鬥争的能力了。你的自信程度同樣也可以被量化，我們用 mc (1 <

= mc <= 100)來表示你的自信值上限。在第i天（i>=1），大佬會對你發動一次嘲諷，使你的自信值減小a[i]，如

果這個時刻你的自信值小于0了，那麼你就喪失鬥争能力，也就失敗了（特别注意你的自信值為0的時候還可以繼續

和大佬鬥争）。在這一天，大佬對你發動嘲諷之後，如果你的自信值仍大于等于0，你能且僅能選擇如下的行為之

一：

1.還一句嘴，大佬會有點驚訝，導緻大佬的自信值C減小1。

2.做一天的水題，使得自己的目前自信值增加 w[i],并将新自信值和自信值上限 mc比

較，若新自信值大于mc，則新自信值更新為mc。例如，mc=50，目前自信值為40，若

w[i]=5，則新自信值為45，若w[i]=11，則新自信值為50。

3.讓自己的等級值L加1。

4.讓自己的諷刺能力F乘以自己目前等級L，使諷刺能力F更新為F*L。

5.怼大佬，讓大佬的自信值C減小F。并在怼完大佬之後，你自己的等級L自動降為0，諷刺能力F降為1。

由于怼大佬比較掉人品，是以這個操作隻能做不超過2次。特别注意的是，在任何時候，你不能讓大佬的自信值為

負，因為自信值為負，對大佬來說意味着屈辱，而大佬但凡遇到屈辱就會進化為更厲害的大佬直接虐飛你。在第1

天，在你被攻擊之前，你的自信是滿的（初始自信值等于自信值上限mc），你的諷刺能力F是1，等級是0。現在由

于你得罪了大佬，你需要準備和大佬正面杠，你知道世界上一共有m（1<=m<=20）個大佬，他們的嘲諷時間都是 n

天，而且第 i天的嘲諷值都是 a[i]。不管和哪個大佬較量，你在第i天做水題的自信回漲都是w[i]。這m個大佬中

隻會有一個來和你較量（n天裡都是這個大佬和你較量），但是作為你，你需要知道對于任意一個大佬，你是否能

摧毀他的自信，也就是讓他的自信值恰好等于0。和某一個大佬較量時，其他大佬不會插手。

Input

第一行三個正整數n,m,mc。分别表示有n天和m個大佬,你的自信上限為mc。

接下來一行是用空格隔開的n個數，其中第i(1<=i<=n)個表示a[i]。

接下來一行是用空格隔開的n個數，其中第i(1<=i<=n)個表示w[i]。

接下來m行，每行一個正整數，其中第k(1<=k<=m)行的正整數C[k]表示第k個大佬的初

始自信值。

1 ≤n,mc ≤100; 1≤m≤20; 1≤a[i],w[i]≤mc; 1≤C[i] ≤10

Output

共m行，如果能戰勝第k個大佬（讓他的自信值恰好等于0），那麼第k行輸出1，否則輸出0。

Sample Input

10 20 100

22 18 15 16 20 19 33 15 38 49

92 14 94 92 66 94 1 16 90 51

4

5

9

338

5222

549

7491

9

12

3288

3

1

2191

833

3

6991

2754

3231

360

6

Sample Output

1

1

1

1

1

1

1

1

1

題解

這題好神啊。

首先仔細觀察幾種操作，發現和自己的自信值有關的隻有一個

是以，自己死不死與怼大佬無關。

是以，相當于拆成兩個部分，一個是怼大佬，另外一個是讓自己的自信值大于 0 0

是以，我們先做一次dpdp，求出最多可以空出多少天來怼大佬，也就是刷水題的最少次數。

這樣，恢複自信與怼大佬兩個分開，互相不影響。

現在的問題就變成了給你 N N 天，能否怼死大佬

我們怼大佬隻與兩個因素有關：天數和嘲諷值。

是以，求出所有的可行的天數和嘲諷值的集合，按照嘲諷值從大到小排序。

不怼或者怼一次解決大佬的情況很容易判斷（如果你隻判斷這個就可以拿到4040分了。。）

現在要解決的問題是怼兩次大佬。

不妨設兩次怼大佬花費的天數分别是 d1,d2 d 1 , d 2 ，總共可以怼 D D 天

嘲諷值分别是f1,f2f1,f2

我們可以列出不等式：

f1+f2<=C,f1+f2+(D−d1−d2)>=C f 1 + f 2 <= C , f 1 + f 2 + ( D − d 1 − d 2 ) >= C

考慮按照 f f 為第一關鍵字，dd為第二關鍵字排序，

現在維護兩個指針，分别從大往小和從小往大枚舉，每次保證 fi+fj<=C f i + f j <= C

因為我們固定了一個方向，不妨固定了 fi f i

是以，此時的定值是 fi,di,D,C f i , d i , D , C

那麼，這個時候要求的就是 f2−d2 f 2 − d 2 的最大值

在從小到大掃的過程中，顯然是單調的，是以不需要再從頭開始掃，直接繼承上一次的指針位置繼續向後即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 111
#define ft(i) (zt[i].first)
#define sd(i) (zt[i].second)
inline int read()
{
    RG int x=,t=;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*+ch-,ch=getchar();
    return x*t;
}
int f[MAX][MAX];
int n,m,MC,Day,a[MAX],w[MAX],C[MAX];
struct Node{int i,F,L;};
pair<int,int> zt[];
int tot,mx;
int MOD=;
struct Hash
{
    struct Line{int x,y,next;}e[];
    int h[+],cnt;
    void Add(int x,int y)
    {
        int pos=(l*x*+y)%MOD;
        e[++cnt]=(Line){x,y,h[pos]};h[pos]=cnt;
    }
    bool Query(int x,int y)
    {
        int pos=(l*x*+y)%MOD;
        for(int i=h[pos];i;i=e[i].next)
            if(e[i].x==x&&e[i].y==y)return true;
        return false;
    }
}Map;
void BFS()
{
    queue<Node> Q;Q.push((Node){,,});
    while(!Q.empty())
    {
        Node u=Q.front();Q.pop();
        if(u.i==Day)continue;
        Q.push((Node){u.i+,u.F,u.L+});
        if(u.L>&&l*u.F*u.L<=l*mx&&!Map.Query(u.F*u.L,u.i+))
        {
            Q.push((Node){u.i+,u.F*u.L,u.L});
            zt[++tot]=make_pair(u.F*u.L,u.i+);
            Map.Add(u.F*u.L,u.i+);
        }
    }
}
int main()
{
    n=read();m=read();MC=read();
    for(int i=;i<=n;++i)a[i]=read();
    for(int i=;i<=n;++i)w[i]=read();
    for(int i=;i<=m;++i)mx=max(mx,C[i]=read());
    for(int i=;i<=n;++i)
        for(int j=a[i];j<=MC;++j)
        {
            f[i][j-a[i]]=max(f[i-][j]+,f[i][j-a[i]]);
            f[i][min(j-a[i]+w[i],MC)]=max(f[i-][j],f[i][min(j-a[i]+w[i],MC)]);
        }
    for(int i=;i<=n;++i)
        for(int j=;j<=MC;++j)Day=max(Day,f[i][j]);
    BFS();sort(&zt[],&zt[tot+]);
    for(int i=;i<=m;++i)
    {
        if(C[i]<=Day){puts("1");continue;}
        bool fl=false;int mm=;
        for(int j=tot,k=;j;--j)
        {
            while(k<tot&&ft(k)+ft(j)<=C[i])
                mm=min(mm,sd(k)-ft(k)),++k;
            if(mm+C[i]-ft(j)<=Day-sd(j)){fl=true;break;}
            if(ft(j)<=C[i]&&C[i]-ft(j)<=Day-sd(j)){fl=true;break;}
        }
        fl?puts("1"):puts("0");
    }
    return ;
}