区间动态规划(Interval Dynamic Programming,简称 IDP)是一种动态规划算法,用于解决包含区间状态的优化问题。在区间动态规划中,问题可以划分为多个不重叠的区间,每个区间可以独立求解,并且状态在相邻区间之间是独立的。
区间动态规划的基本思想是将原问题转化为一系列子问题,每个子问题只涉及一个区间,然后使用动态规划算法求解每个子问题。在求解每个子问题的过程中,可以使用状态转移方程来更新区间状态。
下面是一个简单的例子,说明如何使用区间动态规划求解区间和问题。假设给定一个整数数组 nums 和一个整数 m,要求找到一个连续的子数组,使得该子数组的和不超过 m,并且该子数组的长度最大。
int maxSubArrayLen(int m, int n, int* nums)
{
int dp[n+1][m+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
if (i == 1)
{
dp[i][j] = dp[i-1][j];
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1]);
}
}
}
return dp[n][m];
}
在这个例子中,我们使用二维数组 dp 来保存状态,其中 dp[i] [j] 表示在前 i 个元素中选择不超过 j 的最大和。初始状态为 dp[0] [0] = 0。然后我们使用两个嵌套的循环来遍历所有可能的状态,对于每个状态,我们可以使用状态转移方程来更新它。最后返回 dp[n] [m] 即可得到最大和不超过 m 的最长子数组的长度。
需要注意的是,在实际应用中,需要根据具体问题来设计状态转移方程和初始化状态。同时,还需要考虑如何处理边界条件和特殊情况。
1.环形石子
将n堆石子绕圆形操场排放,现在要将石子有序合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆,并且新的一堆石子数记作该次合并的得分。
请编写一个程序,读入堆数n及每堆的石子数,并进行如下计算:
输入格式:
第一行包含整数n,表示共有n堆石子。
第二行包含n个整数,分别表示每堆石子的数量。
可以将数据变成两倍,从而实现所有的序列。
-
迭代式
for(int len = 1;len <= n; len++) for(int L = 1;L + len - 1 <= n; L++) R = L + len - 1;
-
记忆化搜索
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 410, INF = 0x3f3f3f3f;
int n;
int s[N], w[N];
int f[N][N], g[N][N];
int main()
{
scanf("%d", &n);
for(int i = 1;i <= n; i++)
{
scanf("%d", &w[i]);
w[i + n] = w[i];
}
for(int i = 1;i <= n * 2; 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 * 2; l++)
{
int r = l + len - 1;
if(len == 1)
f[l][r] = g[l][r] = 0;
else
{
for(int k = 1;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 minv = INF, maxv = -INF;
for(int i = 1;i <= n; i++)
{
minv = min(minv, f[i][i + n - 1]);
maxv = max(maxv, g[i][i + n - 1]);
}
cout << minv << endl << maxv << endl;
return 0;
}
2.能量项链
在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链,在项链上有 NN 颗能量珠。
能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。
并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。
因为只有这样,通过吸盘(吸盘是 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。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。
输入格式
输入的第一行是一个正整数 N,表示项链上珠子的个数。
第二行是 N 个用空格隔开的正整数,所有的数均不超过 1000,第 i 个数为第 i 颗珠子的头标记,当 i<N 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记,第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。
至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 210;
int n;
int w[N];
int f[N][N];
int main()
{
cin >> n;
for(int i = 1;i <= n; i++)
{
cin >> w[i];
w[i + n] = w[i];
}
for(int len = 3;len <= n + 1; len++)
for(int l = 1;l + len - 1 <= n * 2; l++)
{
int r = len + l - 1;
for(int k = l + 1;k < r; k++)
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
int res = 0;
for(int i = 1;i <= n; i++) res = max(res, f[i][i + n]);
cout << res << endl;
return 0;
}
3.凸多边形的规划
给定一个具有N个顶点的凸多边形,将顶点从1至N标号,每一个顶点的权重都是一个·正整数。
将这个多项式划分成N-2个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘。
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int w[N];
int f[N][N][M];
void add(LL a[], LL b)
{
static LL c[M];
memset(c, 0, sizeof(c));
for(int i = 0, t = 0;i < M; i++)
{
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof(c));
}
void mul(LL, a[], LL b)
{
static LL c[M];
memset(c, 0, sizeof(c));
LL t = 0;
for(int i = 0;i < M; i++)
{
t += a[i] * b;
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, size(c));
}
int cmp(LL a[], LL b[])
{
for(int i = 0;i < m; i++)
if(a[i] > b[i]) return 1;
else if(a[i] < b[i]) return -1;
return 0;
}
void print(LL a[])
{
int k = M - 1;
while(k && |a[k]) k--;
while(k >= 0) cout << a[k--];
cout << endl;
}
int main()
{
scanf("%d", &n)
for(int i = 1;i <= n; i++)
cin >> w[i];
LL temp[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][M - 1] = 1;
for(int k = l + 1;k < r; k++)
{
memset(temp, 0, sizeof(temp));
temp[0] = w[l];
mul(temp, w[k]);
mul(temp, w[r]);
add(temp, f[l][k]);
add(temp, f[k][r]);
if(cmp(f[l][r], temp) > 0)
memcpy(f[l][r], temp, sizeof(temp));
}
}
print(f[1][n]);
return 0;
}
4.加分二叉树
是一个n个节点的二叉树tree的中序遍历为(1,2,3,4,......,n),其中的数字1,2,3,4,......,n为节点。
每个结点都有一个分数(均为正整数),记作第i个节点的分数为d,tree及它的每一个子树都有一个加分,任意模子树subtree(也包含tree本身)的加分计算方法如下:
subtree的左子树的加分 * subtree的右子树的加分 * subtree的根的分数
若某个子树为空,规定其加分为1,叶子的加分就是叶结点本身的分数,不考虑它的空子树。
试求一棵符合中序遍历为(1,2,3,4,......,n)且加分最高的二叉树tree。
要求输出:
-
tree的最高加分项
-
tree的前序遍历
输入格式:
第一行:一个整数n,为节点个数
第二行:n个用空格隔开的整数,为每个节点的分数(分数<100)
闫氏DP分析法:
动态规划:
-
状态表示f[l,r]:
-
集合:所有中序遍历是[l,r]这一段的二叉树的集合
-
属性:max
-
-
状态计算:w[u] + tree[r] * tree[l]
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 30;
int n;
int w[N];
int g[N][N];
int f[N][N];
void dfs(int l, int r)
{
if(l < r) return;
int root = g[l][r];
cout << root << ' ';
dfs(l, root - 1);
dfs(root + 1, r);
}
int main()
{
cin >> 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;
}
else
{
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;
}
5.棋盘分割
将一个 8×8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了 (n−1) 次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。
现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差
,其中平均值
,xi 为第 i 块矩形棋盘的总分。
请编程对给出的棋盘及 n,求出均方差的最小值。
输入格式
第 1 行为一个整数 n。
第 2 行至第 9 行每行为 8 个小于 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
闫氏DP分析法:
动态规划:
-
状态表示f[x1, y1, x2, y2]
-
集合:将子矩阵(x1, y1)(x2, y2)切分成k部分的所有方案
-
属性是
最小值
-
-
状态计算
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 15, M = 9;
const double INF = 1e9;
int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double x;
double get(int x1, int y1, int x2, int y2)
{
double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] - s[x1 - 1][y1 - 1] -x;
return sum * sum / n;
}
double dp(int x1, int y1, int x2, int y2, int k)
{
int &v = f[x1][y1][x2][y2][k];
if(v >= 0) return v;
if(k == 1) return v = 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, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
}
for(int i = y1;i < y2; i++)
{
v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
}
return v;
}
int main()
{
cin >> 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];
}
memset(f, -1, sizeof(f));
x = s[n][m] / n;
printf("%.3lf\n", dp(1, 1, 8, 8, n));
return 0;
}
子矩阵的和
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 15, M = 9;
const double INF = 1e9;
int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double X;
double get(int x1, int y1, int x2, int y2)
{
double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - X;
return sum * sum / 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 v = 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, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
}
for(int i = y1;i < y2; i++)
{
v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
}
return v;
}
int main()
{
cin >> 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];
}
memset(f, -1, sizeof(f));
X = (double)s[m][m] / n;
printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n)));
return 0;
}