MoXq

分类

题解(6)

/ 注册

全部文章（共4篇）

题解 | #Strategic game#

Strategic game 题意：给你一棵树，已知于某点放一个士兵，则与之相连的边就都能被“看守”，问使所有边都能有人看守至少要放置多少士兵。（本题为多组输入）【与“没有上司的舞会”神似，经典树形dp】思路：树形dp为类似“树的后序遍历”的dfs, 由叶结点向根结点转移。一条边要被看守，...

C++ 动态规划

2022-12-27

1 397

题解 | #滑雪#

这题动规如果用递推来实现的话，就得按点由低到高确定（先给点排序）... 如果用记忆化搜索来写，就可以避免上述顺序的麻烦惹特别注意的是边界的处理呀，当访问到列或行是0的时候是不要赋值f[tx][ty]为1的qwq #include<iostream> #include<algor...

C++ 动态规划

2022-05-21

5 322

[NOPI2002]过河卒

是入门级动规呀把马的位置置0即可，注意边界（窝是直接++，弄堵“墙”保护数组） xdm记得开long long !（其余没啥大事儿了）润~ ">using namespace std; int n,m,x,y; long long f[50][50]; int dx[]={0,2,1,-1,-2,...

C++ 动态规划

2022-05-21

1 329

题解 | #舔狗舔到最后一无所有#

看见有同学问就写一下题解简单DP 思路：因为题目要求连续三天不去同一家，所以我们只需要考虑第i-1天和i-2天情况即可状态表示： f[0/1/2][i]前i天去第0/1/2家购买方案状态计算 f[0][i]=f[1][i-1]+f[2][i-1]+f[1][i-2]+f[2][i-2] f...

动态规划

2022-01-22

32 1579