Liveddd's Blog

愛にできることはまだあるかい

DP 专项训练

发表于 更新于 分类于
本文字数： 9k 阅读时长 ≈ 20 分钟

可以说是 DP 乱做。

先做几道真题。

1.P7077 [CSP-S2020] 函数调用

很明显各个函数的调用关系是一张 DAG。假如只有函数 2，我们就只需要 dfs 一遍就可以求出所有函数的 $mul_i$。我们并不好处理先进行函数 1 再进行函数 2 的情况。于是我们考虑再求出一个 $add_i$ 表示调用完所有函数后第 $i$ 个数的增量。

容易想到在拓扑序 DP 来求这个东西。其实想要求 $add$ 数组很简单，乘 $k$ 也看作将该函数被执行 $k$ 次，我们只需要求出每个函数被执行了多少次，这个我们用 $f_i$ 表示函数 $i$ 被执行了多少次。

因为我们是按照拓扑序来考虑每个函数，而非函数本来的执行顺序。所以我们需要先考虑 $f$ 的初值。$res$ 是一个动态维护的值，表示在第 $i$ 个执行的函数被执行了 $res$ 次（注意上文所说的“被执行”）。对于三种类型的函数分开讨论：1.直接加上 $res$；2.用 $res$ 乘上 $mul_{fuc_i}$（不用加上 $res$，因为我们们根本不关心函数 2 的 $f$ 值）；3.先加上 $res$ ，再用 $res$ 乘上 $mul_{fuc_i}$。

接着我们考虑 DP，设当前节点为 $x$。还是对于三种类型的函数分开讨论：1.直接计算 $add_{pos_x}$；2.根本不用管；3.我们尝试倒序遍历其所有出点，就像上面求初值一样来处理所有出点的 $f$ 值，只不过不需要讨论类型，还有最开始的 $res$ 的值应该为 $f_x$ 。

似乎就这样做完了。。。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int N=1e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c){putchar(c);}
template <>
inline void write(const char *s){while(*s)putchar(*s++);}
template<class T,class ...T1>
inline void write(T x,T1 ...x1){write(x),write(x1...);}

int n,m,q;
int a[N],fuc[N];
int type[N],pos[N],val[N];
int deg[N];
ll mul[N],f[N],add[N];
vector<int>e[N];
void dfs(int x)
{
    mul[x]=(type[x]==2)?val[x]:1;
    int si=e[x].size();
    for(int i=0;i<si;i++)
    {
        int y=e[x][i];
        if(!~mul[y])dfs(y);
        mul[x]=mul[x]*mul[y]%mod;
    }
}
inline void topo()
{
    queue<int>q;
    for(int i=1;i<=m;i++)
        if(!deg[i])
            q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(type[x]==1)
        {
            add[pos[x]]=(add[pos[x]]+val[x]*f[x])%mod;
            continue;
        }
        ll res=f[x];
        int si=e[x].size();
        for(int i=si-1;~i;i--)
        {
            int y=e[x][i];
            f[y]=(f[y]+res)%mod;
            res=res*mul[y]%mod;
            if(!--deg[y])q.push(y);
        }
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
        read(a[i]);
    read(m);
    for(int i=1;i<=m;i++)
    {
        read(type[i]);
        mul[i]=-1;
        if(type[i]==1)read(pos[i],val[i]);
        else if(type[i]==2)read(val[i]);
        else
        {
            int c;
            read(c);
            for(int j=1;j<=c;j++)
            {
                int x;
                read(x);
                e[i].push_back(x);
                deg[x]++;
            }
        }
    }
    for(int i=1;i<=m;i++)
        if(!deg[i])
            dfs(i);
    read(q);
    for(int i=1;i<=q;i++)
        read(fuc[i]);
    ll res=1;
    for(int i=q;i;i--)
    {
        int x=fuc[i];
        if(type[x]==1)f[x]=(f[x]+res)%mod;
        else if(type[x]==2)res=res*mul[x]%mod;
        else f[x]=(f[x]+res)%mod,res=res*mul[x]%mod;
    }
    topo();
    for(int i=1;i<=n;i++)
        write((1ll*a[i]*res+add[i])%mod,' ');
    return 0;
}

2.P7961 [NOIP2021] 数列

注意到 $n,m$ 的范围，应该是个高维 DP。

先设计状态，将我们不太好处理的东西直接记录入状态：比如 $1$ 的个数和进位的问题，设 $f_{i,j,k,p}$，意为前 $i$ 个数选取 $j$，$1$ 的个数为 $k$，先高一位进位 $p$ 的方案数。

从之前的状态转移到当前状态显然不好搞，所以考虑从当前状态向之后的状态进行转移。同时最后一层枚举 $t$，表示选 $t$ 个 $i$。似乎很容易得到状态的转移：

因为权值是一个乘积和的形式，我们也可以尝试拆贡献，也可以比较容易得到：$v_i^t\times C_{n-j}^{t}$。然后就转移就可以了。时间复杂度$\mathcal O(n^4m)$。

其实还可以用滚动数组优化一下，但影响不大。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=40,M=110;
const int mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n,m,a,pos=1;
ll ans;
ll v[M],sum[M][N],C[N][N];
ll f[2][N][N][N];
inline void init()
{
    for(int i=0;i<N;i++)
        C[i][0]=1;
    for(int i=1;i<N;i++)
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
inline int popcnt(int x)
{
    int res=0;
    while(x)res+=x&1,x>>=1;
    return res;
}
int main()
{
    init();
    read(n,m,a);
    for(int i=0;i<=m;i++)
    {
        read(v[i]);
        sum[i][0]=1;
        for(int j=1;j<=n;j++)
            sum[i][j]=sum[i][j-1]*v[i]%mod;
    }
    f[0][0][0][0]=1;
    for(int i=0;i<=m;i++)
    {
        memset(f[pos],0,sizeof(f[pos]));
        for(int j=0;j<=n;j++)
            for(int k=0;k<=a;k++)
                for(int p=0;p<=n>>1;p++)
                    for(int t=0;t<=n-j;t++)
                        f[pos][j+t][k+(t+p&1)][t+p>>1]=(f[pos][j+t][k+(t+p&1)][t+p>>1]
                            +f[pos^1][j][k][p]*sum[i][t]%mod*C[n-j][t]%mod)%mod;
        pos^=1;
    }
    for(int k=0;k<=a;k++)
        for(int p=0;p<=n>>1;p++)
            if(k+popcnt(p)<=a)
                ans=(ans+f[pos^1][n][k][p])%mod;
    printf("%lld\n",ans);
    return 0;
}

3.P3953 [NOIP2017 提高组] 逛公园

我们很容易想到用 DP，并且注意观察 $k$ 的值很小，考虑可以将其记录进状态。设 $f_{x,k}$ 表示从 $1$ 走到点 $x$ ，长度为最短路 $+k$ 的路径数量。 考虑建反图然后记忆化搜索。设边为 $(x,y,z)$，转移很显然有：

如何判 $0$ 环呢，只需要开一个数组判断一下会不会递归到我们需要求解的状态就可以了。

其实似乎也可以递推求解，状态与上面相似，需要按照 $dis$ 从小到大的顺序转移。只不过对于有 $0$ 的边，需要以拓扑序为第二关键字进行转移。稍微麻烦一点。

下面是记忆化搜索的代码。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+10,M=2e5+10,K=60;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Edge
{
    int v,w;
};
int T,n,m,k,p;
vector<Edge>e1[N],e2[N];
int dis[N],vis[N];
int flag,f[N][K],v[N][K];
void SPFA()
{
    queue<int>q;
    q.push(1);
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0,vis[1]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        int si=e1[x].size();
        for(int i=0;i<si;i++)
        {
            int y=e1[x][i].v,z=e1[x][i].w;
            if(dis[x]+z<dis[y])
            {
                dis[y]=dis[x]+z;
                if(!vis[y])q.push(y),vis[y]=1;
            }
        }
    }
}
int dp(int x,int k)
{
    if(k<0||flag)return 0;
    if(v[x][k])
    {
        flag=1;
        return 0;
    }
    if(f[x][k])return f[x][k];
    int ans=0,si=e2[x].size();
    v[x][k]=1;
    for(int i=0;i<si;i++)
    {
        int y=e2[x][i].v,z=e2[x][i].w;
        ans=(ans+dp(y,dis[x]+k-dis[y]-z))%p;
    }
    v[x][k]=0;
    return f[x][k]=ans;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n,m,k,p);
        for(int i=1;i<=n;i++)
            e1[i].clear(),e2[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            read(u,v,w);
            e1[u].push_back({v,w});
            e2[v].push_back({u,w});
        }
        SPFA();
        flag=0;
        memset(f,0,sizeof(f));
        dp(1,0);//注意这个细节，是用来判 0 环的
        f[1][0]=1;//因为我们需要赋初值，但是赋完我们就不能判断经过 1 的 0 环了，所以上面需要先跑一遍
        int ans=0;
        for(int i=0;i<=k;i++)
            ans=(ans+dp(n,i))%p;
        if(flag)
        {
            puts("-1");
            continue;
        }
        printf("%d\n",ans);
    }
    return 0;
}