题目传送门: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; }
Comments NOTHING