[数据结构与算法]Safety Journey (动态规划)

C - Safety Journey 补题记录

题意：在n个城市组成的完全连通图中存在m条边不连通；
现有一个人在k天时间内，从城市1出发，任意相邻两天不在同一个城市，最后一天回到城市1，这样的路线有几条

思路：设dp[i][j]表示在第i天到达第j个城市的方案数。那么，因为相邻两天不会在同一个城市。因此，如果第i - 1天在第j个城市，则第i天绝对不会到达j城市。反过来考虑，只要第i - 1天不在j城市，那么第i天就可以到j城市去.（看了羽歌Yo大佬的博客所悟）

时间复杂度计算：最外层k天，里层含三部分（目的 ： 第i天到达城市j的方案数 = 第i - 1天到达除了城市j的方案数 - 第i - 1天到达的城市无法到达城市j的方案数）O(k * (2 * n + m))

注意：对两数相减的取余的形式为（x - y + MOD） % MOD;

上代码：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 5010, MOD = 998244353;

int u[N], v[N];
LL dp[N][N];

int main()
{
    int n, m, k;
    scanf("%d %d %d",&n, &m, &k);

    for(int i = 1 ; i <= m ; i++)
        scanf("%d %d",&u[i], &v[i]);

    dp[0][1] = 1; //初始在城市1

    for(int i = 1 ; i <= k ; i++)
    {
        LL sum = 0;
        for(int j = 1 ; j <= n ; j++) sum = (sum + dp[i - 1][j] + MOD) % MOD;
        for(int j = 1 ; j <= n ; j++) dp[i][j] = (sum - dp[i - 1][j] + MOD) % MOD;
        for(int j = 1 ; j <= m ; j++)
        {
            dp[i][u[j]] = (dp[i][u[j]] - dp[i - 1][v[j]] + MOD) % MOD;
            dp[i][v[j]] = (dp[i][v[j]] - dp[i - 1][u[j]] + MOD) % MOD;
        }
    }

    printf("%lld\n",dp[k][1]);//最后一天在城市1

    return 0;
}