ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

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

2022年3月20日 682点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: abc atcoder C++ DP 动态规划 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号