[AtCoder Beginner Contest 244]E – King Bombee(DP动态规划)

发布于 2022-03-20  840 次阅读


题目传送门:E - King Bombee (atcoder.jp)

没错,就是一个纯纯的DP,难在状态表示。

一开始我也以为是图论,但是观察到特点:取模、数据范围、奇偶性、求方案数。这些可都是DP的显著特征啊,于是考虑使用dp。

题目描述请看原题,自己翻译一下。

思路

这题难就难在表示状态,我们用dp[i][j][k]表示第i个点,在时间j(时间就是在序列中的位置),走过x的次数为奇数或偶数(1奇数,0偶数)

我们将边存下来,离线处理,每次dp都是遍历所有边

表示完成之后就可以写状态转移方程了,不难发现,转移过程应该分两类,设边为[U, V],我们举例单向边的,双向边也一样。

我们观察到这两个方程的差别其实不大,而且是0 和 1相反的操作,就可以将U == X引入到下标中去,减少代码量,也提高逻辑性。

既然万事俱备了,直接敲代码吧~

记得取模!

代码

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define pr printf
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
int readInt()
{
	int s = 0, w = 1;char ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-')w = -1;ch = getchar();}
	while('0' <= ch && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
	return s * w;
}
typedef pair<int, int> PII;
const int maxn = 2010, p = 998244353;
int N, M, K, S, T, X;//N点,M边,构造K长度的路径,ST起点终点,X点出现偶数次 
PII v[maxn];
int dp[maxn][maxn][2];//dp[点][时间][次数] 

signed main()
{
	cin >> N >> M >> K >> S >> T >> X;
	for(int i = 1;i <= M; ++ i)v[i] = {readInt(), readInt()};
	dp[S][0][0] = 1;
	for(int i = 0;i < K; ++ i)//时间为i
		for(int j = 1;j <= M; ++ j)
		{
			int x = v[j].fi, y = v[j].se;
			for(int k = 0;k <= 1; ++ k)
			{
				(dp[y][i + 1][k] += dp[x][i][k ^ (x == X)]) %= p;
				(dp[x][i + 1][k] += dp[y][i][k ^ (y == X)]) %= p;
			}	
		}
	cout << dp[T][K][0] << '\n';
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09