【解题报告】动态规划进阶题(区间DP、树形DP、状压DP入门)
程序员文章站
2024-03-23 21:36:46
...
南华大学20级ACM队进阶动态规划练习解题报告
1.石子合并(区间DP)
题目链接：Acwing 石子合并
题目分析：最后合并的石子堆的最优解可以分解为求合并前两堆石子的最优解，母问题可以被分解为子问题解决，因此可以选择DP解决
//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 7;
int n;
int a[N];
int s[N]; //前缀和数组
int dp[N][N]; //dp[i][j]代表i~j区域之间的最优解
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], s[i] = s[i - 1] + a[i];
for (int le = 2; le <= n; le++) //枚举区间长度，区间长度最小为2
{
for (int i = 1; i + le - 1 <= n; i++) //枚举起点
{
dp[i][i + le - 1] = 1e8;
for (int j = i; j <= i + le - 1; j++)
{ //枚举区间所有的合并方式，找出最优解
dp[i][i + le - 1] = min(dp[i][i + le - 1], dp[i][j - 1] + dp[j][i + le - 1] + s[i + le - 1] - s[i - 1]);
}
}
}
//输出答案
cout << dp[1][n] << endl;
}
int main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
solve();
return 0;
}
2.环形石子合并(环形区间DP)
题目链接：LibreOJ 能量项链
题目分析：这题与上一题的区别就是区间由直线变成了环形，而解决环形问题的方法就是将原数组复制一份使数组长度变为两倍，然后处理方法与第一题相同。
//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 7;
int n;
int a[N]; //原数组
int s[N]; //前缀和
int dp[N][N]; //最小值
int dp2[N][N]; //最大值
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], s[i] = s[i - 1] + a[i];
for (int i = 1; i <= n; i++) //数组延长为两倍
s[i + n] = s[n + i - 1] + a[i];
int ma = -0x3f3f3f3f;
int mi = 0x3f3f3f3f;
mem(dp, 0x3f); //初始化dp数组
mem(dp2, -0x3f);
for (int le = 1; le <= n; le++) //枚举长度
{
for (int i = 1; i + le - 1 <= 2 * n; i++) //枚举起点，记得枚举到2*n
{
if (i == i + le - 1)
dp[i][i + le - 1] = dp2[i][i + le - 1] = 0;
else
for (int j = i; j < i + le - 1; j++)
{ //枚举所有可能合并情况
dp[i][i + le - 1] = min(dp[i][i + le - 1], dp[i][j] + dp[j + 1][i + le - 1] + s[i + le - 1] - s[i - 1]);
dp2[i][i + le - 1] = max(dp2[i][i + le - 1], dp2[i][j] + dp2[j + 1][i + le - 1] + s[i + le - 1] - s[i - 1]);
}
}
}
for (int i = 1; i + n - 1 <= 2 * n; i++) //找出最大值
{
ma = max(ma, dp2[i][i + n - 1]);
mi = min(mi, dp[i][i + n - 1]);
}
cout << mi << endl;
cout << ma << endl;
}
int main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
solve();
return 0;
}
3.能量项链(环形区间DP)
题目链接：LibreOJ 能量项链
题目分析：环形区间的处理方法与上一题类似，此题虽然说每一个项链有两个值，但是由于前一个柱子的后值必定等于后一个珠子，因此我们依然可以直接dp处理，只是枚举的长度必须从3开始。
//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> PII;
const int N = 210;
int n;
int dp[N][N],w[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
w[i + n]=w[i];
}
mem(dp, 0);
for (int len = 3; len <= n + 1; len++)
{
for (int l = 1; l - 1 + len <= n * 2; l++)
{
int r = l - 1 + len;
for (int k = l + 1; k < r; k++)
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + w[l] * w[k] * w[r]); //两个区间合并后要加上三个数字之积
}
}
int res = 0;
for (int i = 1; i <=2* n; i++) //找出最大值输出
res = max(res, dp[i][i + n]);
cout << res << endl;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
4.二叉苹果树(树形DP)
题目链接：LibreOJ 二叉苹果树
题目分析：背包问题的变种，选取某件物品与选择另外的物品是有相关性的，其中还涉及到了邻接表的存图与遍历问题，第一次写还是有一定难度的。
邻接表知识点：链式前向星代码分析
//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> PII;
const int N = 110,M=N*2;
int n, m;
int h[N], e[M], w[M], ne[M], id; //邻接表所需数组与变量
int dp[N][N];
void add(int a, int b, int c) //邻接表的增加，在这里就不解释了
{
w[id] = c;
e[id] = b;
ne[id] = h[a];
h[a] = id;
id++;
}
void dfs(int u, int fa)
{
for (int i = h[u];~ i; i = ne[i])//i遍历了所有的u的子节点
{
if (e[i] == fa)continue;//这是想认爹做子的逆子，由于存图时当作无向图处理，所以要把重边跳过
dfs(e[i], u);
for (int j = m; j >= 0; j--)//体积,选几条边
{
for (int k = 0; k < j; k++)
{ //遍历子节点判断是否在最后的答案中加上以i为根节点的子树，背包模型
dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[e[i]][k] + w[i]);
}
}
}
}
void solve()
{
cin >> n >> m;
mem(h, -1); //初始化h数组，邻接表知识点
for (int i = 0; i < n - 1; i++)
{
int a, b, c;
cin >> a >> b >> c;
//无向图存图方法，与上面判断是否为逆子对应
add(a, b, c);
add(b, a, c);
}
dfs(1, -1); //1为父节点，h[1]=-1
cout << dp[1][m];
}
int main()
{
//关闭同步流
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
5.没有上司的舞会(树形DP)
题目链接：LibreOJ 周年纪念晚会
题目分析：代码模板与上一题类似，但是状态转移方程需要做出改变，在代码中，我们要实现如果选择了某个领导，那他的直系下司就不会来参加舞会；如果上司不来，我们要判断他的直系下司到底来不来对最后的结果最有利。我们在dp数组中加一个深度为2的维度通过0，1来判断领导来不来。
//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> PII;
const int N = 6500;
int n;
int h[N], e[N], ne[N],id=1; //邻接表
int hasBoss[N]; //用来寻找谁是没有上司的总经理
int happy[N]; //每个人的快乐程度
int dp[N][2]; //dp[i][0],dp[i][1]分别代表i号员工不来和来的最大快乐值
int boss; //总经理的号码，根节点
void add(int a, int b)
{
e[id] = b;
ne[id] = h[a];
h[a] = id++;
hasBoss[b] = 1;
}
void dfs(int u) //u为员工编号
{
dp[u][1] = happy[u]; //u号员工来，就加上他的快乐值
for (int i = h[u]; i != -1; i = ne[i]) //邻接表的遍历
{
dfs(e[i]); //递归
dp[u][1] += dp[e[i]][0]; //u来了，直系下属就都不来
dp[u][0] += max(dp[e[i]][0], dp[e[i]][1]); //u不来，判断一下直系员工来或不来更加有利
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> happy[i];
mem(h, -1);
for (int i = 1; i <= n-1; i++)
{
int x, y;
cin >> x >> y;
add(y, x);
}
for (int i = 1; i <= n; i++) //寻找boss
if (!hasBoss[i])boss = i;
dfs(boss);
cout << max(dp[boss][0], dp[boss][1]);
}
int main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
solve();
return 0;
}
6.国王(状压DP)
题目链接：LibreOJ 国王
题目分析：所谓状压，就是把图中每一行放不放棋子的状态用01二进制数存下来化为dp数组的一个维度，这样就用一个数字存下了一行的状态。大大节省了时间与空间。我们还可以用二进制运算来实现题目中的对放棋子的限制。然后，如果我们能确定第1~i行的情况，第i+1行的情况只与第i行的摆放方法有关，所以我们的dp方程的推导是由前一层得来。所以，我们除了要列出1~n层的情况外，还要列出第0行和n+1行。因为第一行的情况要由第0行推出。而题目最后的答案，就存在n+1行什么也不放的情况中。
如在代码中：
1.一行不能连着放两个国王----(state >> i & 1) && (state >> i + 1 & 1)!=1;
2.周围8个点不能放国王对下一行的限制----(a & b) && check(a | b)!=1;
提示：dp数组要开 long long,下方代码是使用了“ #define int long long ”才看不到long long
//#pragma gcc optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define int long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int, int> pii;
const int N = 12,M=1<<10,K=110;
int n, m;
vector<int> state;
vector<int> head[M];
int cnt[M];
int dp[N][K][M]; //dp[i][j][k]---->前i行总共放了j个国王，第i行摆放情况为k的方案数
bool check(int state) //检查同一行有没有连续放两个国王的函数
{
for (int i = 0; i < n; i++)
if ((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}
int count(int state) //返回一行中国王个数的函数
{
int res = 0;
for (int i = 0; i < n; i++)
res += state >> i & 1;
return res;
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < 1 << n; i++) //把所有符合条件1的二进制数存下来
{
if (check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
}
for(int i=0;i<state.size();i++) //然后再存下对于每一个符合条件1的数的所符合条件2的数
for (int j = 0; j < state.size(); j++)
{
int a = state[i], b = state[j];
if (!(a & b) && check(a | b))
head[i].push_back(j);
}
dp[0][0][0] = 1; //第0层只能有什么都不放这一个选项的一种可能性
for(int i=1;i<=n+1;i++) //第i排
for(int j=0;j<=m;j++) //总共摆j个，相当于背包容积
for(int a=0;a<state.size();a++) //枚举第i行所有行摆放合法情况
for (int b=0;b<head[a].size();b++) //b代表i-1行对应a的合法摆放情况
{
int c = cnt[state[a]]; //c代表合法情况a的摆放的棋子的数量
if (j >= c) //如果背包容积大于物品
dp[i][j][a] += dp[i - 1][j - c][b]; //状态转移求方案数
}
cout << dp[n + 1][m][0] << endl; //输出结果，题目最后的答案就存在n+1行什么也不放的情况中。
}
signed main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
solve();
return 0;
}
练习时间：2021.7.20
作者：Avalon·Demerzel