HDU 5807 Keep In Touch(DP)
文章目录
题目描述
$n$ 个点的DAG,三个人要求位于三个两两点权差值不超过 $K$ 的点
每次三个人可以停止任务或者沿着边同时移动一步,求合法路线的方案数
$n \le 60$
$q \le 2.5 \times 10^5$
简要做法
设 $f(i,j,k)$ 表示三个人分别在 $(i,j,k)$ 时接着往下走的方案数
枚举每个人的下一步位置进行转移
状态数 $O(n^3)$,每个状态的转移时间复杂度为 $O(n^3)$
总时间复杂度 $O(n^6 + q)$
拆解一步转移的过程:三个人同时选择下一步位置 -> 第一个人先选,第二个人再选,第三个人最后选
考虑加维,设 $f(i,j,k,now)$ 表示三个人分别在 $(i,j,k)$ 时,目前准备走 $now$ 这个人的方案数
枚举 $now$ 这个人的下一步位置进行转移。
三个人都走了一步后,再将不符合点权差值限制的状态排除
状态数 $O(n^3)$,每个状态的转移时间复杂度为 $O(n)$
总时间复杂度 $O(n^4 + q)$
参考代码
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <math.h>
#define int long long
const int N = 60 + 5;
const int P = 998244353;
int n, m, K, q;
int w[N], f[N][N][N][3];
bool G[N][N];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while ('0' > ch or ch > '9')
f = ch == '-' ? -1 : 1, ch = getchar();
while ('0' <= ch and ch <= '9')
x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
signed main()
{
// freopen("agent.in", "r", stdin), freopen("agent.out", "w", stdout);
for (int T = read(); T--;)
{
memset(G, 0, sizeof G), memset(f, 0, sizeof f);
n = read(), m = read(), K = read(), q = read();
for (int i = 1; i <= n; i++)
w[i] = read();
for (int i = 1, u, v; i <= m; i++)
u = read(), v = read(), G[u][v] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
f[i][j][k][0] = (abs(w[i] - w[j]) <= K and abs(w[i] - w[k]) <= K and abs(w[j] - w[k]) <= K);
for (int i = n; i >= 1; i--)
for (int j = n; j >= 1; j--)
for (int k = n; k >= 1; k--)
for (int l = 1; l <= n; l++)
{
if (G[i][l] and f[i][j][k][0])
(f[i][j][k][0] += f[l][j][k][1] % P) %= P;
if (G[j][l])
(f[i][j][k][1] += f[i][l][k][2] % P) %= P;
if (G[k][l])
(f[i][j][k][2] += f[i][j][l][0] % P) %= P;
}
for (int x, y, z; q--;)
x = read(), y = read(), z = read(), printf("%lld\n", f[x][y][z][0] % P);
}
return 0;
}