xw的妙妙屋

1.杨辉三角递推法求组合数 设 $C[i][j]$ 为已在 $i$个元素中抽取了 $j$ 个元素，对于上一步描述，有可能是： 这一步没有抽取元素，之前已经抽了 $j$ 个元素：$C[i-1][j]$ 这一步抽取了一个元素，之前已经抽了 $j-1$ 个元素：$C[i-1][j-1]$ 将这两种情况加起来便是 $C[i][j]$ 的结果，由此得出式子： $C[i][j] = C[i-1][j] + C[i-1][j-1]$ 时间复杂度：$O(n^2)$ 核心代码 1234567891011121314151617void getC(int N){ for (int i = 0; i <= N; i++) { for (int j = 0; j <= i; j++) { if (j == 0) { C[i][j] = 1; } else {...

把某周做过的题稍微整理了一下，主要是DP，方便随时复习，也方便后人踩坑。 1 完全背包 · 洛谷 P1616 疯狂的采药 思路 把「时间」看成背包容量，「价值」就是药草收益。每种药草可以无限次采集 ⇒ 完全背包。 状态转移 1dp[j] = max(dp[j], dp[j - h[i]] + w[i]) 代码 12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;const int N = 1e4 + 10;typedef long long ll;int h[N], w[N];const int M = 1e7 + 10;ll dp[M];int main(){ int t, m; scanf("%d%d", &t, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &...