[AtCoder Beginner Contest 265]E – Warp(dp + set)

发布于 2022-08-24  344 次阅读


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

题意 / Problem

在二维平面中,从原点(0, 0)出发,进行N次移动,每次移动可以选择3个方向,分别是从\((x, y)\)移动到\((x + A, y + B)、(x + C, y + D)、(x + E, y + F)\),只在整数点上运动。

有M个障碍点是不能走的。问N次移动后一共可以有多少种运动轨迹。

思路 / Thought

首先考虑怎么快速的判断一个大范围的点是否是障碍点,可以通过set这个数据结构来存储障碍点,再通过set.count({x, y})来判断(x, y)是否是障碍点,插入和查询的复杂度都是O(logM)。

看一下数据范围,\(N \le 300\),所以\(O(N ^ 3)\)的空间复杂度是可以接受的。

定义dp[t][i][j]表示一共走了t步,第一个方向i步,第二个方向j步,第三个方向可以算出来是\(k = t - i - j\)步,有了步数可以算出当前位置,然后再往三个方向拓展,判断是否可以走到,再将当前方案加到后面的点里面去。

\(dp[t + 1][i + (g == 0)][j + (g == 1)] = (dp[t + 1][i + (g == 0)][j + (g = 1)] + dp[t][i][j]) \% p\)

代码 / Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int maxn = 303, p = 998244353;
int dp[maxn][maxn][maxn];// dp[n][x][y]
set<pair<int, int> > del;//不能达到的点 


void solve()
{
	int N, M;cin >> N >> M;
	vector<pair<int, int> > dir;//direction方向
	for(int i = 0;i < 3; ++ i)
	{
		int x, y;cin >> x >> y;
		dir.push_back({x, y});
	} 
	while(M --)
	{
		int x, y;cin >> x >> y;
		del.insert({x, y});
	}
	dp[0][0][0] = 1;
	for(int t = 0;t <= N; ++ t)//一共走了t次 
		for(int i = 0;i <= t; ++ i)//第一个方向 
			for(int j = 0;i + j <= t; ++ j)//第二个方向 
			{
				int k = t - i - j;
				int x = dir[0].fi * i + dir[1].fi * j + dir[2].fi * k;
				int y = dir[0].se * i + dir[1].se * j + dir[2].se * k;
				for(int g = 0;g < 3; ++ g)//下一个方向 
				{
					int nx = x + dir[g].fi, ny = y + dir[g].se;
					if(!del.count({nx, ny}))
						dp[t + 1][i + (g == 0)][j + (g == 1)] = (dp[t + 1][i + (g == 0)][j + (g == 1)] + dp[t][i][j]) % p;
				}
			}
	int ans = 0;
	for(int i = 0;i <= N; ++ i)
		for(int j = 0;i + j <= N; ++ j)
			ans = (ans + dp[N][i][j]) % p;
	cout << ans << '\n'; 
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while(_ --)solve();
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-08-26