Zhuwanxing

分类

dp(2) 剑指offer(3) 题解(7)

/ 注册

全部文章（共5篇）

郊区春游

https://ac.nowcoder.com/acm/problem/16122 旅行商问题(板子题):每个城市都得经过且仅经过一次通过数据范围和题目模型容易看出是旅行商问题，故直接状压dp(刚开始还傻不拉几的用并查集写QAQ)思路(旅行商问题的常见状态设置):状态表示:dp[st][i]:走过...

比赛题解

2021-05-09

0 915

Most Powerful

https://ac.nowcoder.com/acm/problem/15832数据范围不超过10，每种原子的有与无很容易用二进制表示，故明显是状压dp 状态表示dp[i]：当前所有原子的状态为i的所有方案的最大能量值状态计算dp[i] = max(dp[j] + w[p][q])(当前最后一个消...

比赛题解

2021-05-07

1 439

Strategic game

题目大意对于任意一条边，其都只有两种被覆盖的可能:1.被上面的节点(父节点)覆盖2.被下面的节点(子节点)覆盖故容易推出状态表示和方程dp[i][j]:以i为根的子树的所有边被覆盖且i的状态为j的所有方案的数量最小值(j = 0表示i不放士兵，j = 0为i放士兵)转移方程dp[i][0] = ∑...

比赛题解

2021-04-27

3 540

Cell Phone Network

树的最小支配集问题题目大意：思路:对于任意一个点，只有三种被覆盖的情况1.被自己覆盖2.被自己的子节点覆盖3.被自己的父节点覆盖故很容易推出状态表示dp[i][j]:以i为根的子树的全部节点被覆盖且i节点的覆盖状态为j的所有方案的节点最小值(其中j = 0表示被自己覆盖，j = 1表示被儿子覆盖，...

比赛题解

2021-04-26

1 500

牛客练习赛78题解

比赛题解

2021-03-12

19 1487