2018.2.8 dp专题

考试

由于本次考试本人是验题人，故没有心路历程与代码
题目推荐:新魔法药水(预处理很复杂的完全背包),小a和uim之大逃离(差值dp)

T1 Generals

其实题目已经说得很清楚了，$a_i<b_i$就不可能出现环，并且($$)

对于20%

数据暴搜所有可能的路径,统计答案即可，注意可能不走路也可以成为一种情况
时间复杂度（？？？）

对于40%

我们会很容易想到dp[i][[x1][x2][0/1]表示走到i号点有x1个tyh和x2个ljl的方案数,0/1表示当前节点时获得了tyh还是ljl，按拓扑序跑一遍dp，最后统计答案即可。时空复杂度(m*k*k)
如果你打得足够优秀可以过60%

对于100%

然后我们发现我们其实不需要记录每一个x1,x2的情况，我们只需要开一个$dp[i][x][0/1]$,记录x1,x2的差值x，就可以转移状态并统计答案，时空复杂度(m*k)期望得分100.(注意：细节很重要，会让你wa到wa的一声就哭了)

while(!Q.empty())
{
    ll u=Q.front();Q.pop();
    for(ll i=head[u];i;i=a[i].next)
    {
        ll v=a[i].to;
        for(ll z=0;z<=k;z++)
        {
            dp[v][z][0]=(dp[v][z][0]+dp[u][(z-c[v]+k)%k][1])%mod;
            dp[v][z][1]=(dp[v][z][1]+dp[u][(z+c[v]+k)%k][0])%mod;
        }
        ru[v]--;
        if(!vis[v]&&!ru[v])
        {
            vis[v]=1;
            Q.push(v);
        }
    }
    vis[u]=0;
}

T2 Math

其实与比它小的所有数与它最大公约数为1就是说这个数是质数(滑稽)

对于20%

打一个3位素数表，穷举所有n位数，判断统计，或者在考场上跑出来，直接暴力输入输出，可以拿到20分

对于40%

其实我也不知道什么能跑40% 但总有些奇奇怪怪的算法能跑过，于是就给了这一档部分分。

对于100%

我们可以想到，每一个n位优美数，它的后n-1位拼在一起也是一个优美数，所以我们只要判断这前三位组成的三位数是否是个一个设一个dp[i][k]表示i位数前两位为的优美数的个数。转态转移就很容易想到了
时空复杂度(n*100)

for(int now=4;now<=n;now++)
    {
        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++)
            {
                for(int k=1;k<=9;k++)
                {
                    if(pd(i+10*j+100*k))
                    {
                        dp[now][j][i]=(dp[now][j][i]+dp[now-1][k][j])%mod;
                    }
                }
            }
        }
    }

对于附加分

我们会发现，其实每次状态转移方式都没有任何区别，于是，我们可以构建一个状态矩阵，跑一遍矩阵快速幂即可拿到150分
时间复杂度(10^6*log n)
空间复杂度(10000)

T3 Dance

对于10%

暴搜即可
时空复杂度(???)

对于30%

加一些优化应该可以过(出题人也不知道这档分怎么拿)

对于100%

我们可以想到，开一个$p[i][j]$表示已经踏到i号箭头，并且已经累计踏了j个箭头的最大分数，以k结束其实就可以当作以k位根节点，从儿子向父亲转移，但是这道题也有许多细节，注意处理好就能拿到100分
（这题由于数据都是rand的，所以可能有一些奇奇怪怪的错误算法获得了高分，不要惊讶）

for(int i=a[u];i;i=nex[i])
{
    int v=to[i];
    if(v==fa)continue;
    dfs(u,v);
    dp[u][0]=max(dp[u][0],max(dp[v][0]-s[u],dp[v][t-1]+s[u]+b[u]));
    for(int j=1;j<=t;++j)
        dp[u][j]=max(dp[u][j],max(dp[v][j-1]+s[u],dp[v][j]-s[u]));
}

T4 Magic

对于10%

输出0即可

对于30%

其实出题人也不知道你是怎么拿到的，拿到的话说明你的暴搜很优秀

对于另外20%

注意到m=0的情况，那就是一个裸的完全背包(不解释)

对于100%

首先，直接使用完全背包进行转移的，那么恭喜你你只有20分
因为这样你是没有考虑到魔法套魔法的情况，即为了使用第i个魔法，我将破格使用j个亏损的魔法，但是第i个魔法带来的利润足以弥补之前所有损失。因而这个题目没有那么简单，说白了你就要来个复杂的预处理再进行完全背包
那么考虑利用两个辅助dp数组进行维护我们所需的答案
$f[u][j]$表示得到第u个药水且使用j次魔法的最大利润值
$r[i][j]$表示完成某个魔法的前i个材料使用j次魔法的最小成本
$dp[i][j][k]$表示在做到了第i个魔法，已经使用了j次魔法，k表示此时使用的钱数下的最大利润（但是为了降低复杂度，必须将第一维滚掉，详情请参考“信息学奥赛一本通”完全背包专讲）
因而我们可以开始考虑转移(注意细节处理就好)
$r[i][j+k]=min\{r[i][j+k],r[i-1][j]+f[a[cao][i]][k]\}(k+j\le K)$
$f[u][j+1]=min\{f[u][j+1],r[shu[cao]][j]\}$
$dp[k][v]=max\{dp[k][v],dp[k-j][v-f[i][j]]+lirun[i]\}$
之外还有一些细节，例如初始化，顺序等等(具体可参考std或G1-Zhoukaijun)
总而言之，还是一道很优秀的dp,符合出题人风格

int len=g[u].size();
for(rg int sc=0;sc<len;sc++)
{
    rg int cao=g[u][sc];
    mem(r,63);
    r[0][0]=0;
    for(rg int i=1;i<=shu[cao];i++)
    {
        for(rg int j=0;j<=K;j++)
        {
            for(rg int k=0;k+j<=K;k++)
            {
                r[i][j+k]=Min(r[i][j+k],r[i-1][j]+f[a[cao][i]][k]);
            }
        }
    }
    for(rg int j=0;j<K;j++)
    {
        f[u][j+1]=Min(f[u][j+1],r[shu[cao]][j]);
    }
}
for(rg int i=1;i<=N;i++)
{
    for(rg int j=0;j<=K;j++)
    {
        for(rg int k=j;k<=K;k++)
        {
            for(rg int v=f[i][j];v<=V;v++)
            {
                dp[k][v]=Max(dp[k][v],dp[k-j][v-f[i][j]]+li[i]);
                ans=Max(ans,dp[k][v]-v);
            }
        }
    }
}