题解 P3724 [AHOI2017/HNOI2017]大佬

· · 题解

解题思路

暴力打法

这个题一看题面和题目，令人畏惧，但是细细读题后可以发现：好像就是个深搜，再一看数据范围，直接开码 （然后我们愉快的TLE40pts）。

code

正解

有一个十分重要的地方就是怼大佬与活下来是两个事。

然后我们就可以分别运算了：

DP最多天数

类似于背包 DP ，利用前面的更新现在的直接 +1 就好了，最后对于所有的 dp 值取 mod ，求出最大天数就好了。

void get_Day()
{
    for(int i=1;i<=n;i++)//枚举天数
        for(int j=a[i];j<=mc;j++)//枚举自己的自信
        {
            dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
            int temp=min(mc,j-a[i]+w[i]);
            dp[i][temp]=max(dp[i][temp],dp[i-1][j]);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=mc;j++)
            day=max(day,dp[i][j]);
}

BFS求二元组(d,f)

二元组 (d,f) 表示第 d 天 (d<D) 并且此时的 F=f ，运算的过程中需要去重，用 Hash 或者 map 可以很好的解决这个问题这里给出 map 做法。

队列的数组三维分别表示: 天数， L ，F，对于大于上面求的D，直接跳过，其他的枚举并更新 L 和 F 入队就好了，然后用一个 S1 数组储存所有的二元组。

void get_Dui()
{
    int head=1,tail=0;
    q[++tail]=make_pair(1,make_pair(0,1));
    a1[make_pair(1,1)]=1;
    while(head<=tail)
    {
        pair<int,pair<int,int> > temp;
        temp=q[head++];
        if(temp.first>=day)
            continue;
        int da=temp.first,l=temp.second.first,f=temp.second.second;
        q[++tail]=make_pair(da+1,make_pair(l+1,f));
        a1[make_pair(da+1,f)]=1;
        if(l>1&&l*f<=mxc&&!a1[make_pair(da+1,l*f)])
        {
            int new_f=l*f;
            q[++tail]=make_pair(da+1,make_pair(l,new_f));
            a1[make_pair(da+1,new_f)]=1;
            s1[++cnt]=make_pair(da+1,new_f);
        }
    }
}

算法主体

显然，可以怼没大佬自信值的情况有三种：

  1. 一次都不怼，仅用 1 操作消磨他并且 C_i\le D 。
  2. 只怼一次大佬，剩下的拿 1 来凑，这是需要有一个二元组 (d,f) 满足 f\le C_i ,并且 f+D-d\ge C_i
  3. 怼两次大佬，两次分别为 (d_1,f_1) 和 (d_2,f_2) 并且满足f_1+f_2 \le C_i 和 f_1+f_2-d_1-d_2+D \ge C_i。 诚然，对于同一个 f 只有最小的 d 是最优的，因此我们只需要对于每一个 f 保存最小的 d 就好了， map 有一次正好的满足了这个条件（那还用Hash干嘛）,然后我们双向指针扫一下，再判断一小下就可以过掉此题了。

题目对于各项要求比较严格，具体实现细节见代码。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+10,M=3e6+10,INF=1e9;//注意数组大小 
int n,m,mc,mxc,a[N],w[N],c[25];
int tot,cnt,day,dp[N][N];
pair<int,int> s1[M],s2[M];
pair<int,pair<int,int> > q[M];//day l f
map<pair<int,int>,int> a1;
map<int,bool> a2;
void get_Day()//求出最大的day 
{
    for(int i=1;i<=n;i++)//类似于背包dp 
        for(int j=a[i];j<=mc;j++)
        {
            dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
            int temp=min(mc,j-a[i]+w[i]);
            dp[i][temp]=max(dp[i][temp],dp[i-1][j]);
        }
    for(int i=1;i<=n;i++)//取最值 
        for(int j=1;j<=mc;j++)
            day=max(day,dp[i][j]);
}
void get_Dui()//求二元组(d,f) 
{
    int head=1,tail=0;
    q[++tail]=make_pair(1,make_pair(0,1));
    a1[make_pair(1,1)]=1;
    while(head<=tail)
    {
        pair<int,pair<int,int> > temp;
        temp=q[head++];
        if(temp.first>=day)
            continue;
        int da=temp.first,l=temp.second.first,f=temp.second.second;
        q[++tail]=make_pair(da+1,make_pair(l+1,f));
        a1[make_pair(da+1,f)]=1;
        if(l>1&&l*f<=mxc&&!a1[make_pair(da+1,l*f)])
        {
            int new_f=l*f;
            q[++tail]=make_pair(da+1,make_pair(l,new_f));
            a1[make_pair(da+1,new_f)]=1;
            s1[++cnt]=make_pair(da+1,new_f);
        }
    }
}
bool comp(pair<int ,int > x,pair<int ,int > y)//重新定义sort排序规则 
{
    if(x.second==y.second)
        return x.first<y.first;
    return x.second<y.second;
}
#undef int
int main()
{
    #define int register long long
    #define ll long long
    scanf("%lld%lld%lld",&n,&m,&mc);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&c[i]);
        mxc=max(mxc,c[i]);
    }
    get_Day();
    get_Dui();
    sort(s1+1,s1+cnt+1,comp);
    for(int i=1;i<=cnt;i++)
        if(!a2[s1[i].second])
        {
            a2[s1[i].second]=true;
            s2[++tot]=s1[i];
        }
    for(int k=1;k<=m;k++)
    {
        if(c[k]<=day)//一次也不怼 
        {
            printf("1\n");
            continue;
        }
        bool vis=false;
        int pos=1;
        for(int i=tot;i>=1;i--)
        {
            int da=s2[i].first,f=s2[i].second;
            if(f<=c[k]&&day-da+f>=c[k])
            {
                vis=true;
                break;
            }
            int maxn=-INF;
            while(pos<=tot&&f+s2[pos].second<=c[k])
            {
                maxn=max(maxn,s2[pos].second-s2[pos].first);//如果是int，应该把+f卸载循环里不然会爆掉 
                pos++;
            }
            if(f-da+maxn>=c[k]-day)//判断符合条件 
            {
                vis=true;
                break;
            }
        }
        printf("%d\n",vis?1:0);
    }
    return 0;
}