首页 > 网格图

__故人__

发表于 2020-09-09 16:14:57

分析对于一个节点从恰好走步走到之类的都可以用来处理。定义代表第步，到节点，当前方向是的总方案数。那么一个节点可以从个方向转移过来，再枚举自己的方向。时间复杂度为。还有第一维可以用滚动数组优化空间。代码 #include<bits/stdc++.h&g 展开全文

DeNeRATe

发表于 2020-09-09 18:44:04

分析由于所以我们可以直接考虑较为大胆的算法直接枚举，将其暴力直接转移需要注意的就是，每次的转移方向需要判断一下当时，我们只能转移相同方向上的方案由于空间问题，我们最好使用滚动数组转移时间复杂度：代码 //Newcoder 16735 #include <iostream> #inc 展开全文

Dear㉿You

发表于 2020-09-09 20:20:38

题目分析我的第一个想法是bfs(QwQ),不用说，肯定凉凉。思考，对于一个点( i , j )，如果和小B的切比雪夫距离大于D，那么肯定可以转移到 ( i , j )的四个方向，也可以停留原地。但是如果小于等于D时，肯定只能单方向转移或是停留原地这样我们就可以写出dp方程了设f[ t 展开全文

Zxsoul

发表于 2021-09-15 21:38:43

【网格图.题解】思路对于图表类问题，给多少信息就直接放在 DP 维度中就好了，由于题目中新填了一个限制，所以对于当前的位置来说，可能需要知道上一次转移的具体信息，所以在开一维度记录有那个方向的数转移而来表示到且是由的方向转移而来的方案数，那么答案就是对于我们有五中状态展开全文

issue是云哥的小迷×呀

发表于 2020-10-04 15:07:12

一眼感觉转移,但是状态炸了然后想到线性,但没有明显的转移顺序所以可以考虑把步数设进状态,这样最外层只需要循环即可转移又因为转移牵涉到上一次的移动方向所以设表示走了步,目前在位置,利用方向走到当前位置的转移很显然了 #include <iostream> #include < 展开全文

查看本题

查看本题讨论

等你来战

查看全部