區(qū)間dp一般是先枚舉區(qū)間長度，再枚舉左端點，再枚舉分界點，時間復雜度為

環(huán)形石子合并

將?n?堆石子繞圓形操場排放，現(xiàn)要將石子有序地合并成一堆。

規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)記做該次合并的得分。

請編寫一個程序，讀入堆數(shù)?n?及每堆的石子數(shù)，并進行如下計算：

• 選擇一種合并石子的方案，使得做?n?1 次合并得分總和最大。
• 選擇一種合并石子的方案，使得做?n?11?次合并得分總和最小。

輸入格式

第一行包含整數(shù)?n，表示共有?n?堆石子。

第二行包含?n?個整數(shù)，分別表示每堆石子的數(shù)量。

輸出格式

輸出共兩行：

第一行為合并得分總和最小值，

第二行為合并得分總和最大值。

數(shù)據(jù)范圍

1≤n≤200

輸入樣例：

4
4 5 9 4

輸出樣例：

43
54

?考了把環(huán)拆成鏈，把兩個數(shù)組拼在一起可以達成 類環(huán) 的效果

比如 1 2 3 4 1 2 3 4

環(huán)可以是[1 2 3 4] [2 3 4 1] [3 4 1 2] [4 1 2 3]

這樣就可以在石子合并的基礎上增加微量時間復雜度的情況下做這道題了

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;
typedef pair<ll, int> PII;const int N = 410;int n;
int w[N], s[N];
int f[N][N], g[N][N];int main()
{IOScin >> n;for(int i = 1; i <= n; i ++){cin >> w[i];w[i + n] = w[i];}for(int i = 1; i <= n + n; i ++){s[i] = s[i - 1] + w[i];}memset(f, 0x3f, sizeof f);memset(g, -0x3f, sizeof g);for(int len = 1; len <= n; len ++){for(int l = 1; l + len - 1 <= n + n; l ++){int r = l + len - 1;if(len == 1){f[l][r] = g[l][r] = 0;continue;}for(int k = l; k < r; k ++){f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);}}}int maxn = -2e9, minx = 2e9;for(int i = 1; i <= n; i ++){maxn = max(maxn, g[i][i + n - 1]);minx = min(minx, f[i][i + n - 1]);}cout << minx << endl;cout << maxn;return 0;
} 

能量項鏈

在 Mars 星球上，每個 Mars 人都隨身佩帶著一串能量項鏈，在項鏈上有?N?顆能量珠。

能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。

并且，對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。

因為只有這樣，通過吸盤（吸盤是 Mars 人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。

如果前一顆能量珠的頭標記為?m，尾標記為?r，后一顆能量珠的頭標記為?r，尾標記為?n，則聚合后釋放的能量為?m×r×n（Mars 單位），新產生的珠子的頭標記為?m，尾標記為?n。

需要時，Mars 人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。

顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。

例如：設?N=4，4?顆珠子的頭標記與尾標記依次為?(2，3)(3，5)(5，10)(10，2)。

我們用記號?⊕⊕?表示兩顆珠子的聚合操作，(j⊕k) 表示第?j，k?兩顆珠子聚合后所釋放的能量。則

第?4、1 兩顆珠子聚合后釋放的能量為：(4⊕1)=10×2×3=60。

這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為?((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。

輸入格式

輸入的第一行是一個正整數(shù)?N，表示項鏈上珠子的個數(shù)。

第二行是?N?個用空格隔開的正整數(shù)，所有的數(shù)均不超過?1000，第?i?個數(shù)為第?i?顆珠子的頭標記，當?i<N 時，第?i?顆珠子的尾標記應該等于第?i+1 顆珠子的頭標記，第?N?顆珠子的尾標記應該等于第?1?顆珠子的頭標記。

至于珠子的順序，你可以這樣確定：將項鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。

輸出格式

輸出只有一行，是一個正整數(shù)?E，為一個最優(yōu)聚合順序所釋放的總能量。

數(shù)據(jù)范圍

4≤N≤100,
1≤E≤2.1×1e9

輸入樣例：

4
2 3 5 10

輸出樣例：

710

和上一題幾乎一模一樣

可以先枚舉長度，再枚舉首位端點，再枚舉連接點

?我寫的代碼不太一樣，但結果都是一樣的

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;
typedef pair<ll, int> PII;const int N = 210;int n;
int w[N];
ll f[N][N];int main()
{IOScin >> n;for(int i = 1; i <= n; i ++){cin >> w[i];w[i + n] = w[i];}memset(f, -0x3f, sizeof f);for(int len = 1; len <= n; len ++){for(int l = 1; l + len - 1 <= n + n; l ++){int r = l + len - 1;if(len == 1){f[l][r] = 0;continue;}for(int k = l; k < r; k ++){f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + w[l] * w[k + 1] * w[r + 1]);}}}ll ans = -2e18;for(int i = 1; i <= n; i ++){ans = max(ans, f[i][i + n - 1]);}cout << ans;return 0;
} 

加分二叉樹

設一個?n?個節(jié)點的二叉樹 tree 的中序遍歷為（1,2,3,…,n），其中數(shù)字?1,2,3,…,n 為節(jié)點編號。

每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第?i?個節(jié)點的分數(shù)為?di，tree 及它的每個子樹都有一個加分，任一棵子樹 subtree（也包含 tree 本身）的加分計算方法如下：?????

subtree的左子樹的加分?×?subtree的右子樹的加分?＋?subtree的根的分數(shù)?

若某個子樹為空，規(guī)定其加分為?1。

葉子的加分就是葉節(jié)點本身的分數(shù)，不考慮它的空子樹。

試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹 tree。

要求輸出：?

（1）tree的最高加分?

（2）tree的前序遍歷

輸入格式

第?1?行：一個整數(shù)?n，為節(jié)點個數(shù)。?

第?2?行：n?個用空格隔開的整數(shù)，為每個節(jié)點的分數(shù)（0<分數(shù)<100）。

輸出格式

第?1?行：一個整數(shù)，為最高加分（結果不會超過int范圍）。?????

第?2?行：n?個用空格隔開的整數(shù)，為該樹的前序遍歷。如果存在多種方案，則輸出字典序最小的方案。

數(shù)據(jù)范圍

n<30

輸入樣例：

5
5 7 1 2 10

輸出樣例：

145
3 1 2 4 5

?中序遍歷一個數(shù)左邊都是左子樹的部分，一個數(shù)右邊都是右子樹的部分

所以可以用f[l, r]表示[l, r]區(qū)間內所有子樹的最大值，去枚舉每個點當根節(jié)點

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;
typedef pair<ll, int> PII;const int N = 40;int n;
int w[N];
int f[N][N], g[N][N];void dfs(int l, int r)
{if(l > r)return;int t = g[l][r];cout << t << ' ';dfs(l, t - 1);dfs(t + 1, r);
}int main()
{IOScin >> n;for(int i = 1; i <= n; i ++)cin >> w[i];for(int len = 1; len <= n; len ++){for(int l = 1; l + len - 1 <= n; l ++){int r = l + len - 1;if(len == 1){f[l][r] = w[l];g[l][r] = l;continue;}for(int k = l; k <= r; k ++){int left = k == l ? 1 : f[l][k - 1];int right = k == r ? 1 : f[k + 1][r];int score = left * right + w[k];if(f[l][r] < score){f[l][r] = score;g[l][r] = k;}}}}cout << f[1][n] << endl;dfs(1, n);return 0;
}

凸多邊形的劃分

給定一個具有?N?個頂點的凸多邊形，將頂點從?1?至?N?標號，每個頂點的權值都是一個正整數(shù)。

將這個凸多邊形劃分成?N?2 個互不相交的三角形，對于每個三角形，其三個頂點的權值相乘都可得到一個權值乘積，試求所有三角形的頂點權值乘積之和至少為多少。

輸入格式

第一行包含整數(shù)?N，表示頂點數(shù)量。

第二行包含?N個整數(shù)，依次為頂點?1?至頂點?N?的權值。

輸出格式

輸出僅一行，為所有三角形的頂點權值乘積之和的最小值。

數(shù)據(jù)范圍

N≤50,
數(shù)據(jù)保證所有頂點的權值都小于1e9

輸入樣例：

5
121 122 123 245 231

輸出樣例：

12214884

?可以發(fā)現(xiàn)每條邊只會參與一個三角形的構成

以1-n這條邊為底，共有n-2種選法，設選了k這個點為頂點，那左邊1~k和右面k~n兩個區(qū)域明顯是相互獨立的，這就構成了區(qū)間dp的基礎

枚舉選頂點是哪個即可

這題雖然也是環(huán)但不需要拼起來，因為每個邊只參與一次，選1 - n還是選2 - n+1都是一樣的

另外需要用到高精度，可以先當成不需要高精度的寫出來，再改成高精度，這樣輕松一點

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;
typedef pair<ll, int> PII;const int N = 55, M = 35, INF = 2e9;int n;
int w[N];
ll f[N][N][M];//f[l,r]表示以l、r兩點為邊,以中間的一個頂點作為分界線 void add(ll a[], ll b[])
{ll tmp[M] = {0};ll t = 0;for(int i = 0; i < M; i ++){t += a[i] + b[i];tmp[i] = t % 10;t /= 10;}memcpy(a, tmp, sizeof tmp);
}void mul(ll a[], ll b)
{ll tmp[M] = {0};ll t = 0;for(int i = 0; i < M; i ++){t += a[i] * b;tmp[i] = t % 10;t /= 10;}memcpy(a, tmp, sizeof tmp);
}int cmp(ll a[], ll b[])
{for(int i = M - 1; i >= 0; i --){if(a[i] > b[i])return 1;if(a[i] < b[i])return -1;}return 0;
}void print(ll a[])
{ll t = M - 1;while(t && !a[t])t --;for(int i = t; i >= 0; i --)cout << a[i];cout << endl;
}int main()
{IOScin >> n;for(int i = 1; i <= n; i ++)cin >> w[i];ll tmp[M];for(int len = 3; len <= n; len ++){for(int l = 1; l + len - 1 <= n; l ++){int r = l + len - 1;//f[l][r] = INF;f[l][r][M - 1] = 1;for(int k = l + 1; k < r; k ++){memset(tmp, 0, sizeof tmp);tmp[0] = w[l];mul(tmp, w[r]);mul(tmp, w[k]);add(tmp, f[l][k]);add(tmp, f[k][r]);if(cmp(tmp, f[l][r]) < 0){memcpy(f[l][r], tmp, sizeof tmp);}//f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[r] * w[k]);}}}//cout << f[1][n];print(f[1][n]);return 0;
}

棋盤分割

將一個?8×8 的棋盤進行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了?(n?1)次后，連同最后剩下的矩形棋盤共有?n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進行)

原棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和。

現(xiàn)在需要把棋盤按上述規(guī)則分割成?n?塊矩形棋盤，并使各矩形棋盤總分的均方差最小。

均方差

?，其中平均值

?，xi?為第?i?塊矩形棋盤的總分。

請編程對給出的棋盤及?n，求出均方差的最小值。

輸入格式

第?1?行為一個整數(shù)?n。

第?2?行至第?9?行每行為?8?個小于?100 的非負整數(shù)，表示棋盤上相應格子的分值。每行相鄰兩數(shù)之間用一個空格分隔。

輸出格式

輸出最小均方差值（四舍五入精確到小數(shù)點后三位）。

數(shù)據(jù)范圍

1<n<15

輸入樣例：

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

輸出樣例：

1.633

?f[x1][y1][x2][y1][k]表示左上角的點為(x1,y1),右下角的點為(x2,y2)，這塊區(qū)域要被分位k個點，表示均方差平方的最小值

由題可得n確定后平均值X也能確定

枚舉時考慮橫著切還是豎著切，切的時候考慮是留上邊還是下邊、左邊還是右邊

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;
typedef pair<ll, int> PII;const int N = 9, M = 15, INF = 2e9;int n, m = 8;
int s[N][N];
double f[N][N][N][N][M];
double X;double get(int x1, int y1, int x2, int y2)
{double res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] - X;return res * res / n;
}double dp(int x1, int y1, int x2, int y2, int k)
{double &v = f[x1][y1][x2][y2][k];if(v >= 0)return v;if(k == 1)return get(x1, y1, x2, y2);v = INF;for(int i = x1; i < x2; i ++){v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));}for(int j = y1; j < y2; j ++){v = min(v, dp(x1, y1, x2, j, k - 1) + get(x1, j + 1, x2, y2));v = min(v, get(x1, y1, x2, y2) + dp(x1, j + 1, x2, y2, k - 1)); }return v;
}int main()
{//IOScin >> n;for(int i = 1; i <= m; i ++){for(int j = 1; j <= m; j ++){cin >> s[i][j];s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}}X = (double)s[m][m] / n;memset(f, -1, sizeof f);double t = dp(1, 1, m, m, n);printf("%.3lf", sqrt(t));return 0;
}