ErikTse Runtime

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

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

2022年8月24日 163点热度 0人点赞 0条评论

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

Eriktse

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

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

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

文章目录
  • 题意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号