spa dimens 二叉树 乘积最大 pri %d true urn
1. LCS 最长公共子序列
- /* LCS
- * Au: GG
- */
- #include < cstdio > #include < cstdlib > #include < cstring > #include < cmath > #include < ctime > #include < iostream > #include < algorithm > using namespace std;
- const int N = 1005;
- int n,
- m,
- d[N][N],
- A[N],
- B[N];
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
- for (int i = 1; i <= m; i++) scanf("%d", &B[i]);
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- d[i][j] = max(d[i - 1][j], d[i][j - 1]);
- if (A[i] == B[j]) d[i][j] = max(d[i][j], d[i - 1][j - 1] + 1);
- }
- }
- printf("%d\n", d[n][m]);
- return 0;
- }
2. LIS 最长上升自序列
- /**
- * LIS
- * Au: GG
- **/
- #include < cstdio > #include < cstdlib > #include < cmath > #include < iostream > #include < cstring > #include < algorithm > using namespace std;
- const int N = 1000000 + 3;
- int n,
- a[N],
- d[N];
- int ans;
- int main() {
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- scanf("%d", &a[i]);
- }
- for (int i = 1; i <= n; i++) {
- d[i] = 1;
- for (int j = 1; j < i; j++) {
- if (a[i] > a[j] && d[j] + 1 > d[i]) d[i] = d[j] + 1;
- }
- ans = max(ans, d[i]);
- }
- printf("%d\n", ans);
- return 0;
- }
3. 01 背包
- // 01 Knapsack
- // Au: GG
- #include < iostream > #include < cstdlib > #include < cstdio > #include < cmath > #include < cstring > using namespace std;
- int n,
- v,
- w[33],
- f[33][20003];
- int main() {
- scanf("%d%d", &v, &n);
- for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= v; j++) {
- if (j - w[i] < 0) f[i][j] = f[i - 1][j];
- else f[i][j] = max(f[i - 1][j - w[i]] + w[i], f[i - 1][j]);
- }
- }
- printf("%d", v - f[n][v]);
- return 0;
- }
4. 完全背包
- /**
- * Luogu P1616 疯狂的采药
- * Au: GG
- **/
- #include < cstdio > #include < cstdlib > #include < cmath > #include < iostream > #include < cstring > #include < algorithm > using namespace std;
- int n,
- m,
- d[100000 + 4],
- w[100000 + 3],
- v[100000 + 3];
- int main() {
- scanf("%d%d", &m, &n);
- for (int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
- for (int i = 1; i <= n; i++) {
- for (int j = v[i]; j <= m; j++) {
- d[j] = max(d[j], d[j - v[i]] + w[i]);
- }
- }
- printf("%d\n", d[m]);
- return 0;
- }
5. 多维背包
- /**
- * Luogu P1855 榨取kkksc03
- * Au: GG
- **/
- #include < cstdio > #include < cstdlib > #include < cmath > #include < iostream > #include < cstring > #include < algorithm > using namespace std;
- const int N = 100 + 3,
- M = 200 + 3;
- int n,
- m,
- t,
- time[N],
- w[N],
- d[N][M][M];
- int main() {
- scanf("%d%d%d", &n, &m, &t);
- for (int i = 1; i <= n; i++) scanf("%d%d", &time[i], &w[i]);
- for (int i = 1; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- for (int k = 0; k <= t; k++) {
- d[i][j][k] = d[i - 1][j][k];
- if (j - time[i] >= 0 && k - w[i] >= 0 && d[i - 1][j - time[i]][k - w[i]] + 1 > d[i][j][k]) d[i][j][k] = d[i - 1][j - time[i]][k - w[i]] + 1;
- }
- }
- }
- printf("%d\n", d[n][m][t]);
- return 0;
- }
6. 树形 DP (Unaccepted)
7. 区间 DP
- /* Luogu P1880 石子合并
- * Au: GG
- */
- #include < cstdio > #include < cstdlib > #include < cstring > #include < cmath > #include < ctime > #include < iostream > #include < algorithm > using namespace std;
- const int N = 100 + 5;
- const int inf = 2147483647;
- int n,
- d[2 * N][2 * N],
- e[2 * N][2 * N],
- a[N],
- sum[2 * N];
- int ans1 = inf,
- ans2 = -inf;
- int main() {
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
- for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i > n ? i % n: i];
- for (int i = 1; i <= 2 * n; i++) d[i][i] = 0;
- for (int len = 2; len <= n; len++) {
- for (int i = 1; i + len - 1 <= 2 * n; i++) {
- int j = i + len - 1;
- d[i][j] = inf;
- for (int k = i; k < j; k++) {
- d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j] + sum[j] - sum[i - 1]);
- }
- }
- }
- for (int i = 1; i <= n; i++) ans1 = min(ans1, d[i][i + n - 1]);
- for (int i = 1; i <= 2 * n; i++) e[i][i] = 0;
- for (int len = 2; len <= n; len++) {
- for (int i = 1; i + len - 1 < 2 * n; i++) {
- int j = i + len - 1;
- e[i][j] = -inf;
- for (int k = i; k < j; k++) {
- e[i][j] = max(e[i][j], e[i][k] + e[k + 1][j] + sum[j] - sum[i - 1]);
- }
- }
- }
- for (int i = 1; i <= n; i++) ans2 = max(ans2, e[i][i + n - 1]);
- printf("%d\n%d\n", ans1, ans2);
- return 0;
- }
8. 状态压缩 DP (Unaccepted)
9. 例题 (Unaccepted)
#A 传纸条(Accepted)
#B 乘积最大 (Unaccepted)
#C 石子合并 (Accepted)
#D 加分二叉树 (Unaccepted)
#E 没有上司的舞会 (Unaccepted)
#F 选课 (Accepted)
#G 警卫安排 (Unaccepted)
#H 通向自由的钥匙 (Unaccepted)
动态规划 List
来源: http://www.bubuko.com/infodetail-2218192.html