Enzon

分类

题解(4)

/ 注册

全部文章（共4篇）

题解 | #躲藏#

长春某理工acm月赛的某题出处，很难评。正题：我们考虑线性转移，dp[i]表示“Cwbc”中以1~i前字母组成的单词的数量。那么该单词1到i的数量只能由上一个单词1到i-1转移而来，故状态转移为(i=1) dp[i]++, (i>=2)dp[i] += dp[i-1]。由于不区分大小写，故第...

C++ 动态规划

2023-09-20

0 317

题解 | #Magic Maze#

堪称最大连续字段和的图论版本链接https://www.luogu.com.cn/problem/P1115 有向无环图，那么我们可以用拓扑排序，在删边的时候状态转移。 f[v] = max(f[u] + w, f[v]) ans最小设为0，ans = max(ans, f[v]) #inc...

C++ 动态规划

2023-09-18

0 309

题解 | #TaoTao要吃鸡#

数据水了！把楼上的代码改了一下，当h为0的时候，也按背包的方法把第k件物品装上去。 #include<bits/stdc++.h> using namespace std; const int N = 110; int m, n, h; int w[N], v[N]; int f[N]...

C++ 动态规划

2023-09-17

0 339

题解 | #美丽的项链#

知识点：分组背包，01背包一共有n组，每组有物品的体积为l到r的物品，且每组物品有个r - l + 1个。对于一组中的某个物品，我们只能选和不选，则满足01背包条件。每个组只能由上一组的状态转移而来，符合题中n个组都选。定义状态 dp[i][j] 为 1~i 组中，体积为 j 的方案数，转移公式为...

动态规划

2023-09-16

0 319