长春某理工acm月赛的某题出处，很难评。 正题：我们考虑线性转移，dp[i]表示“Cwbc”中以1~i前字母组成的单词的数量。那么该单词1到i的数量只能由上一个单词1到i-1转移而来，故状态转移为(i=1) dp[i]++, (i>=2)dp[i] += dp[i-1]。由于不区分大小写，故第i为既可以是大写也可以是小写。 #include<bits/stdc++.h> #define int long long using namespace std; const int N = 5e5 + 10, mod = 2000120420010122; signed main(...

堪称最大连续字段和的图论版本 链接https://www.luogu.com.cn/problem/P1115 有向无环图，那么我们可以用拓扑排序，在删边的时候状态转移。 f[v] = max(f[u] + w, f[v]) ans最小设为0，ans = max(ans, f[v]) #include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e4 + 10; vector<vector<pair<int, int>>>g; int an...

数据水了！ 把楼上的代码改了一下，当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][N * 2];// 0<=n,m,h<=100 int main() { while (cin >> n) { if (n == 0) break; cin >> m >> h; for (int i = 1; i <= n...

知识点：分组背包，01背包 一共有n组，每组有物品的体积为l到r的物品，且每组物品有个r - l + 1个。对于一组中的某个物品，我们只能选和不选，则满足01背包条件。每个组只能由上一组的状态转移而来，符合题中n个组都选。定义状态 dp[i][j] 为 1~i 组中，体积为 j 的方案数，转移公式为 dp[i][j] += dp[i - 1][j - v]。 ">using namespace std; #define int long long const int mod = 1e9 + 7, N = 1e3 + 10; int f[25][105]; signed main() { io...