# [problem solving report] advanced dynamic programming problem (Introduction to interval DP, tree DP and pressure DP)

Report on advanced dynamic programming practice of ACM team of grade 20 in Nanhua University

### 1. Stone merging (interval DP)

Title Link: Acwing stone merge

Problem analysis: the optimal solution of the last combined pile of stones can be decomposed into the optimal solution of the first two piles of stones, and the parent problem can be decomposed into subproblems to solve, so you can choose DP to solve

```//#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];  //Prefixes and arrays
int dp[N][N];  //dp[i][j] represents the optimal solution between i~j regions

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++)  //Enumeration interval length, the minimum interval length is 2
{
for (int i = 1; i + le - 1 <= n; i++)  //Enumeration starting point
{
dp[i][i + le - 1] = 1e8;
for (int j = i; j <= i + le - 1; j++)
{   //Enumerate all the merging methods of the interval to find the optimal solution
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]);
}
}
}
//Output answer
cout << dp[1][n] << endl;
}

int main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
solve();
return 0;
}
```

### 2. Ring stone merging (ring interval DP)

Title Link: LibreOJ energy Necklace

Problem analysis: the difference between this problem and the previous one is that the interval is changed from a straight line to a ring, and the solution to the ring problem is to duplicate the original array so that the length of the array is doubled, and then the processing method is the same as the first one.

```//#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];  //Original array
int s[N];  //Prefix and
int dp[N][N];  //minimum value
int dp2[N][N];  //Maximum

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++)  //The array is doubled
s[i + n] = s[n + i - 1] + a[i];
int ma = -0x3f3f3f3f;
int mi = 0x3f3f3f3f;
mem(dp, 0x3f);  //Initialize dp array
mem(dp2, -0x3f);
for (int le = 1; le <= n; le++)  //Enumeration length
{
for (int i = 1; i + le - 1 <= 2 * n; i++)   //Enumeration starting point, remember to enumerate to 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++)
{   //Enumerates all possible merges
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++)  //Find the maximum
{
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. Energy Necklace (DP)

Title Link: LibreOJ energy Necklace

Topic analysis: the processing method of circular interval is similar to the previous one. Although this problem says that each necklace has two values, because the latter value of the former column must be equal to the latter bead, we can still directly deal with dp, but the enumeration length must start from 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]);  //After merging two intervals, add the product of three numbers
}
}
int res = 0;
for (int i = 1; i <=2* n; i++)  //Find the maximum output
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. Binary apple tree (tree shape)

Title Link: LibreOJ binary apple tree

Topic analysis: a variant of knapsack problem, the selection of an item is related to the selection of another item, which also involves the storage and traversal of adjacency table, the first time to write or have a certain difficulty.
Adjacency table knowledge points: Chain forward star code analysis

```//#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;  //Arrays and variables required by adjacency table
int dp[N][N];

void add(int a, int b, int c)  //The addition of adjacency table will not be explained here
{
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 traverse all the children of u
{
if (e[i] == fa)continue;//This is the inverse that wants to recognize father as son. Since the graph is treated as an undirected graph when it is saved, it is necessary to skip the double edge
dfs(e[i], u);
for (int j = m; j >= 0; j--)//Volume, how many sides
{
for (int k = 0; k < j; k++)
{   //Traversing the sub nodes to determine whether to add the subtree with i as the root node in the final answer, knapsack model
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);  //Initialize the h array, adjacent table knowledge points

for (int i = 0; i < n - 1; i++)
{
int a, b, c;
cin >> a >> b >> c;
//The undirected graph storage method corresponds to the above judgment of whether it is an inverse
add(a, b, c);
add(b, a, c);
}
dfs(1, -1);  //1 is the parent node, h[1]=-1
cout << dp[1][m];
}

int main()
{
//Turn off synchronization flow
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
```

### 5. Dance without boss (tree shaped DP)

Title Link: LibreOJ anniversary party

Topic analysis: the code template is similar to the previous question, but the state transition equation needs to be changed. In the code, we need to realize that if a leader is selected, his immediate subordinate will not come to the dance; If the boss doesn't come, we have to judge whether his immediate subordinate will come or not, which is the best for the final result. We add a dimension with depth of 2 to the dp array, and judge whether the leader will come or not through 0 and 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;  //Adjacency table
int hasBoss[N];  //Used to find out who is the general manager without a boss
int happy[N];  //How happy everyone is
int dp[N][2];  //DP [i] [0] and DP [i] [1] respectively represent the maximum happiness of employee I who doesn't come and employee I who comes
int boss;  //General manager's number, root node
void add(int a, int b)
{
e[id] = b;
ne[id] = h[a];
h[a] = id++;
hasBoss[b] = 1;
}

void dfs(int u)  //u is the employee number
{
dp[u][1] = happy[u];  //When employee u comes, add his happiness value
for (int i = h[u]; i != -1; i = ne[i])  //Traversal of adjacency table
{
dfs(e[i]);  //recursion
dp[u][1] += dp[e[i]][0];  //When u comes, none of his direct subordinates will come
dp[u][0] += max(dp[e[i]][0], dp[e[i]][1]);  //If you don't come, it's better to judge whether the direct staff will come or not
}
}

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++)  //Looking for 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. King (DP)

Title Link: King LibreOJ

Topic analysis: the so-called shape pressure is to save the status of chess pieces in each line of the graph into a dimension of the dp array with 01 binary number, so as to save the status of a line with a number. Greatly save time and space. We can also use binary operation to realize the restriction of playing chess pieces in the title. Then, if we can determine the case of line 1~i, the case of line i+1 is only related to the placement method of line i, so the derivation of our dp equation is derived from the previous layer. Therefore, in addition to Listing 1~n layers, we also need to list row 0 and row n+1. Because the situation of the first line will be introduced from line 0. And the final answer to the question exists in the case of n+1 line without putting anything.

For example, in the code:
1. You can't put two kings in a row --- (state > > I & 1) & (state > > I + 1 & 1)= 1;
2. You can't put the king's restriction on the next line around the eight points -- (A & B) & check (a | b)= 1;

Tip: the dp array needs to open long long. The code below uses "# define int long long" to see 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] -- > there are j kings in the first row, and the number of schemes with K in the first row

bool check(int state)  //Check if there are two consecutive functions on the same line
{
for (int i = 0; i < n; i++)
if ((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}

int count(int state)  //A function that returns the number of Chinese kings in a row
{
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++)  //Save all binary numbers that meet condition 1
{
if (check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
}

for(int i=0;i<state.size();i++)  //Then save the number that meets condition 2 for each number that meets condition 1
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;  //Layer 0 can only have the possibility of not putting anything
for(int i=1;i<=n+1;i++)  //Row i
for(int j=0;j<=m;j++)   //A total of j, equivalent to the volume of the backpack
for(int a=0;a<state.size();a++)  //Enumerate the legal placement of all lines in line i
for (int b=0;b<head[a].size();b++)  //b represents the legal placement of i-1 line corresponding to a
{
int c = cnt[state[a]];  //c stands for the number of pieces in the legal situation a
if (j >= c)  //If the volume of the backpack is larger than the item
dp[i][j][a] += dp[i - 1][j - c][b];   //Solution number of state transition
}
cout << dp[n + 1][m][0] << endl;   //Output results, the final answer to the question exists in the case of n+1 line without putting anything.

}

signed main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
solve();
return 0;
}
```

Practice time: July 20, 2021
By Avalon Demerzel

Posted by fyg0072 at Jul 20, 2021 - 1:40 PM
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}