动态规划¶
动态规划基础¶
动态规划基础 - OI Wiki (oi-wiki.org)
最长公共子序列¶
for (int i = 1; i <= n;i++) {
for (int j = 1; j <= m;j++)
{
if(a[i] == b[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
res = f[n][m];
最长不下降子序列¶
算法一¶
时间复杂度\(O(n^2)\)
int a[MAXN], d[MAXN];
int dp() {
d[1] = 1;
int ans = 1;
for (int i = 2; i <= n; i++) {
d[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] <= a[i]) {
d[i] = max(d[i], d[j] + 1);
ans = max(ans, d[i]);
}
}
return ans;
}
算法二¶
时间复杂度\(O(nlogn)\)
for (int i = 0; i < n; ++i) scanf("%d", a + i);
memset(dp, 0x1f, sizeof dp);
mx = dp[0];
for (int i = 0; i < n; ++i) {
*std::upper_bound(dp, dp + n, a[i]) = a[i];
}
ans = 0;
while (dp[ans] != mx) ++ans;
子序列个数¶
背包问题¶
状态表示：\(f(i,j)\)
状态计算：集合划分
关键：状态转移方程
0-1背包问题¶
// 0-1背包问题
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int v[N], w[N];
int main()
{
cin >> n >> m;
int i, j;
for (i = 1; i <= n; i++)
{
cin >> v[i] >> w[i];
}
for (i = 1; i <= n; i++)
{
for (j = m; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
int res = 0;
for (i = 1; i <= m; i++)
{
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
完全背包问题¶
\(\(f[j] = max(f[j], f[j - v[i]] + w[i])\)\)
#include<iostream>//完全背包问题
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main()
{
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for (i = 1; i <= n; i++)
{
for (j = v[i]; j <= m; j++)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout<<f[m];
return 0;
}
多重背包问题¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int v[N],w[N],s[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i] >> s[i];
}
for (int i = 1;i<=n;i++)
{
for (int j = m; j >= 0 && j >= v[i];j--)
{
for (int k = 0; k <=s[i]&&k*v[i]<=j;k++)
{
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}
}
}
cout << f[m] << endl;
return 0;
}
二进制优化¶
。。。
混合背包问题¶
for (循环物品种类) {
if (是 0 - 1 背包)
套用 0 - 1 背包代码;
else if (是完全背包)
套用完全背包代码;
else if (是多重背包)
套用多重背包代码;
}
### 二维费用背包 P1855 榨取kkksc03 - 洛谷
区间DP¶
石子合并¶
设有 N 堆石子排成一排，其编号为 1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
Code
read(n);
for (int i = 1; i <= n; i++)
{
read(a[i]);
}
for (int i = 1; i <= n; i++)
{
a[i] += a[i - 1];
}
// len 合并区域的长度
// i + (len - 1) = j
for (int len = 2; len <= n; len++)
{
for (int i = 1; i + len - 1 <= n; i++)
{
int l = i;
int r = i + len - 1;
f[l][r] = 1e8;
for (int k = l; k < r; k++)
{
// (f[l][k] + f[k+1][r]) + (a[r] - a[l - 1]) 合并的成本
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
树形DP¶
没有上司的舞会¶
题目描述
某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式
输入的第一行是一个整数 \(n\)。
第 \(2\) 到第 \((n + 1)\) 行，每行一个整数，第 \((i+1)\) 行的整数表示 \(i\) 号职员的快乐指数 \(r_i\)。
第 \((n + 2)\) 到第 \(2n\) 行，每行输入一对整数 \(l, k\)，代表 \(k\) 是 \(l\) 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
样例 #1
样例输入 #1
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
样例输出 #1
5
提示
数据规模与约定
对于 \(100\%\) 的数据，保证 \(1\leq n \leq 6 \times 10^3\)，\(-128 \leq r_i\leq 127\)，\(1 \leq l, k \leq n\)，且给出的关系一定是一棵树。
- 上司不参加舞会时，下属可以参加，也可以不参加，此时有 \(f(i,0) = \sum max{f(x,1),f(x,0)}\)
- 上司参加舞会时，下属都不会参加，此时有 \(f(i,1) = \sum f(x,0)+a_{i}\)
因此可以使用dfs，从根节点开始遍历树，在返回上一层时更新节点
Code¶
int f[N][2];
int is_h[N];
int h[N], e[N], ne[N], idx;
bool st[N];
void add(int a, int b)
{
idx++;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
void dfs(int k)
{
st[k] = 1;
for (int i = h[k]; i; i = ne[i]) // 枚举该结点的每个子结点
{
int j = e[i];
if (st[j])
continue;
solve(j);
f[k][1] += f[j][0];
f[k][0] += max(f[j][0], f[j][1]); // 转移方程
}
return;
}
int main()
{
IOS;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> f[i][1];
}
for (int i = 1; i < n; i++)
{
int l, k;
cin >> l >> k;
is_h[l] = 1;
add(k, l);
}
for (int i = 1; i <= n; i++)
{
if (!is_h[i]) // 从根结点开始DFS
{
dfs(i);
printf("%d", max(f[i][1], f[i][0]));
return 0;
}
}
return 0;
}
树上背包¶
状压DP¶
相关内容 位运算 最小表示法 - OI Wiki (oi-wiki.org)
互不侵犯
在\(N \times N\)的棋盘里面放\(K\)个国王(1<=N<=9,1<=K<=N * N)，使他们互不攻击，共有多少种摆放方案。
国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
实现
#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;
void dfs(int x, int num, int cur) {
if (cur >= n) { // 有新的合法状态
sit[++cnt] = x;
sta[cnt] = num;
return;
}
dfs(x, num, cur + 1); // cur位置不放国王
dfs(x + (1 << cur), num + 1,
cur + 2); // cur位置放国王，与它相邻的位置不能再放国王
}
bool compatible(int j, int x) {
if (sit[j] & sit[x]) return false;
if ((sit[j] << 1) & sit[x]) return false;
if (sit[j] & (sit[x] << 1)) return false;
return true;
}
int main() {
cin >> n >> k;
dfs(0, 0, 0); // 先预处理一行的所有合法状态
for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= cnt; j++)
for (int x = 1; x <= cnt; x++) {
if (!compatible(j, x)) continue; // 排除不合法转移
for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]];
}
long long ans = 0;
for (int i = 1; i <= cnt; i++) ans += f[n][i][k]; // 累加答案
cout << ans << endl;
return 0;
}