2020-2021:teams:manespace:atcoder_beginner_contest_176
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:manespace:atcoder_beginner_contest_176 [2020/08/28 23:55] iuiou 创建 |
2020-2021:teams:manespace:atcoder_beginner_contest_176 [2020/08/29 20:05] (当前版本) iuiou |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| 题解：老套路题了，一看就是找环，由于数字是循环出现的，所以只要计算一个周期的情况，枚举每一个$dfs$出来得环，对每个环先看一周期下来获得的总和是否大于0，若大于0，则可以重复移动到最后，否则只能在一个周期内移动，否则必定不会是最优的。之后枚举取最大值即可。 | 题解：老套路题了，一看就是找环，由于数字是循环出现的，所以只要计算一个周期的情况，枚举每一个$dfs$出来得环，对每个环先看一周期下来获得的总和是否大于0，若大于0，则可以重复移动到最后，否则只能在一个周期内移动，否则必定不会是最优的。之后枚举取最大值即可。 | ||
| - | =====E | + | =====E Picking Goods===== |
| + | 题意：有一个$n*m$的矩阵，一共有$k$个物品，放在$k$个不同的位置，每个物品都有一个权值。一个人从$(1,1)$点出发，只能向右或者向下走，走到终点$(n,m)$,过程中可以收集沿路的物品，问最终能收集到物品权值最大的方案是什么。 | ||
| + | |||
| + | 题解：整体思想是$dp$，设数组$dp[i][j][k]$表示走到$(i,j)$点在该行已经收集到$k$种物品的答案，每次可以从上一行转移，就是从$dp[i-1][j][k](k=0,1,2,3)$取最大，或者从左边的转移，即考虑$dp[i][j-1][k]$之后采用一般的背包$dp$的思想转移即可。 | ||
2020-2021/teams/manespace/atcoder_beginner_contest_176.1598630114.txt.gz · 最后更改: 2020/08/28 23:55 由 iuiou
