东丰在线网站建设,破解wordpress后台密码,pc 网站建设,自动优化网站建设咨询一、什么是环形DP
环形动态规划#xff08;Circular Dynamic Programming#xff09;是处理环形结构数据的一类特殊DP问题。与线性DP不同#xff0c;环形DP中第一个元素和最后一个元素相邻#xff0c;形成一个闭环。这种结构导致起点和终点可以相互影响#xff0c;增加了…一、什么是环形DP
环形动态规划Circular Dynamic Programming是处理环形结构数据的一类特殊DP问题。与线性DP不同环形DP中第一个元素和最后一个元素相邻形成一个闭环。这种结构导致起点和终点可以相互影响增加了问题的复杂性。
1.1环形DP的核心 循环依赖首尾元素相互影响难以确定起点 状态转移复杂需要考虑跨越首尾边界的情况 解空间扩大最优解可能出现在环上的任意位置
1.2环形问题的通用解法
破环成链法将环形结构转化为线性结构处理 复制原始序列并接在其尾部 在长度为2N的新序列上进行线性DP 计算结果时枚举所有长度为N的区间
二、经典问题1环形石子合并
2.1问题描述
将 n堆石子绕圆形操场排放现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆并将新的一堆的石子数记做该次合并的得分请编写一个程序读入堆数n及每堆的石子数并进行如下计算 1、选择一种合并石子的方案使得做 n-1次合并得分总和最大。 2、选择一种合并石子的方案使得做 n-1次合并得分总和最小
输入格式 输入第一行一个整数 n表示有 n堆石子, 第二行 n个整数表示每堆石子的数量。
输出格式 输出共两行 第一行为合并得分总和最小值第二行为合并得分总和最大值,
输入样例 4 4 5 9 4
输出样例 43 54
对于100%的数据有1≤n≤200
2.2 破环成链
int a[201]; // 原始石子数组
int sum[202]; // 前缀和数组// 复制序列
for(int i 1; i n; i) {cin a[i];a[ni] a[i]; // 复制一份接在尾部
}// 计算前缀和
for(int i 1; i 2*n; i) {sum[i] sum[i-1] a[i];
}
2.3 状态定义
f[i][j]合并区间[i,j]内石子的最小代价
2.4 状态转移方程
f[i][j] min(f[i][j], dfs_min(i, j) dfs_min(i 1, j) sum[j] - sum[i - 1]);
2.5 记忆化搜索实现
int dfs(int begin, int end) {if(f[begin][end]) return f[begin][end]; // 记忆化if(begin end) return 0; // 边界条件int ret MAX_INT;for(int k begin; k end; k) {int cost dfs(begin, k) dfs(k1, end) sum[end] - sum[begin-1];ret min(ret, cost);}f[begin][end] ret; // 存储结果return ret;
}
2.6 完整代码
#include iostream
using namespace std;int sum[202], a[101]; // 声明存储石子总数的数组sum和存储每堆石子数量的数组a
int n; // 存储石子堆数量int f[202][202]; // 用于存储最小得分的动态规划数组
int fmax[202][202]; // 用于存储最大得分的动态规划数组// 计算任意两点之间的最小合并分数和
int dfs_min(int s, int e)
{if (s e)return 0;if (f[s][e])return f[s][e];int ans 0x3f3f3f3f; // 初始化ans为一个较大的值for (int k s; k e; k)ans min(ans, dfs_min(s, k) dfs_min(k 1, e) sum[e] - sum[s - 1]);f[s][e] ans;return ans;
}// 计算任意两点之间的最大合并分数和
int dfs_max(int s, int e)
{if (s e)return 0;if (fmax[s][e])return fmax[s][e];int ans 0;for (int k s; k e; k)ans max(ans, dfs_max(s, k) dfs_max(k 1, e) sum[e] - sum[s - 1]);fmax[s][e] ans;return ans;
}int main()
{cin n; // 输入石子堆数量for (int i 1; i n; i){cin a[i]; // 输入每堆石子数量sum[i] sum[i - 1] a[i]; // 计算前缀和表示前i堆石子总数}// 将前缀和连接成2n-1的链用于求解任意两点之间的合并分数和for (int i 1; i n - 1; i){sum[n i] sum[n i - 1] a[i];}// 求链上任意两点的最小合并分数和和最大合并分数和dfs_min(1, 2 * n - 1);dfs_max(1, 2 * n - 1);int ansmin 0x3f3f3f3f; // 初始化最小值int ansmax 0; // 初始化最大值 // 枚举链上长度为n的区间找出其中的最小值和最大值for (int i 1; i n; i){ansmin min(ansmin, f[i][i n - 1]);ansmax max(ansmax, fmax[i][i n - 1]);}// 输出最小得分和最大得分cout ansmin endl ansmax;return 0;
}三、经典问题2能量项链
3.1 问题描述
环形排列的能量珠每颗珠子有头尾标记。合并相邻珠子释放能量m*r*n其中m为前珠头标记r为前珠尾标记后珠头标记n为后珠尾标记。
3.2 破环成链
int lace[201]; // 存储头标记
cin n;
for(int i 1; i n; i) {cin lace[i];lace[ni] lace[i]; // 复制序列
}
3.3 状态定义
f[i][j]合并区间[i,j]内珠子释放的最大能量
3.4 状态转移方程
f[i][j] max(maxn, search(i, k) search(k1, j) lace[i] * lace[k1] * lace[j1]);
3.5 记忆化搜索实现
int search(int i, int j) {if(f[i][j]) return f[i][j]; // 记忆化if(i j) return 0; // 边界条件int maxn 0;for(int k i; k j; k) {int energy search(i, k) search(k1, j) lace[i] * lace[k1] * lace[j1];maxn max(maxn, energy);}f[i][j] maxn; // 存储结果return maxn;
}
3.6 完整代码
#include iostream using namespace std;
int n; // 存储项链上珠子的个数 int lace[201]; // 存储珠子的标记 int f[202][202]; // 用来存储动态转移方程中的结果 // 函数search搜索从第i到第j颗珠子聚合后释放的能量的最大值 int search(int i, int j) { if(f[i][j]) // 如果f[i][j]已经计算过则直接返回结果 return f[i][j]; if(i j) // 如果i大于等于j说明没有珠子可聚合返回0 return 0; int maxn 0; // 用来记录搜索过程中的最大能量值 for(int k i; k j; k) // 循环遍历所有可能的分割点k maxn max(maxn, search(i, k) search(k1, j) lace[i] * lace[k1] * lace[j1]); // 更新maxn为当前的最大能量值 f[i][j] maxn; // 将计算得到的结果存入f数组中 return maxn; // 返回从第i到第j颗珠子聚合后释放的能量的最大值 } int main() { cin n; // 输入项链上珠子的个数n for(int i 1; i n; i) // 循环读入每颗珠子的标记 { cin lace[i]; // 输入第i颗珠子的头标记 lace[ni] lace[i]; // 将尾标记设置为与头标记相同 } // 将前缀和连接成2n-1的链用于求解任意两点之间的能量和 search(1, 2*n-1); // 调用search函数计算能量释放的最大值 int maxn 0; // 记录最终的最大能量值 for(int i 1; i n; i) // 遍历所有可能的起始位置 maxn max(maxn, f[i][in-1]); // 更新maxn为当前的最大能量值 cout maxn; return 0; }
四、环形DP特点总结
4.1. 状态定义 区间型DPdp[i][j]表示区间[i,j]的最优解 状态含义与线性DP相似但区间长度需考虑环状特性
4.2. 状态转移 枚举分割点k将区间分为[i,k]和[k1,j] 合并代价包含三部分左区间代价 右区间代价 当前合并代价
4.3. 环形处理关键
// 序列复制
for(int i 1; i n; i) {arr[ni] arr[i];
}// 结果枚举
for(int i 1; i n; i) {ans min/max(ans, dp[i][in-1]);
}
4.4. 时间复杂度 状态数O(N²) 每个状态转移O(N) 总时间复杂度O(N³)
五、环形DP扩展应用
5.1. 环形子数组最大和
int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint arr(2*n);// 复制数组for(int i 0; i n; i) {arr[i] arr[in] nums[i];}// DP求解int maxSum INT_MIN;vectorint dp(2*n);for(int i 0; i 2*n; i) {if(i 0) dp[i] arr[i];else dp[i] max(arr[i], dp[i-1] arr[i]);if(i n-1) maxSum max(maxSum, dp[i]);}return maxSum;
}
5.2. 环形房屋盗窃
int robCircular(vectorint nums) {int n nums.size();if(n 0) return 0;if(n 1) return nums[0];// 分两种情况偷第一间和不偷第一间return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1));
}int robRange(vectorint nums, int start, int end) {int dp0 0, dp1 0;for(int i start; i end; i) {int temp max(dp1, dp0 nums[i]);dp0 dp1;dp1 temp;}return dp1;
}
六、环形DP优化技巧
6.1. 单调队列优化
对于某些环形问题可以使用单调队列将时间复杂度优化到O(N)
// 环形滑动窗口最大值
vectorint maxSlidingWindowCircular(vectorint nums, int k) {int n nums.size();vectorint arr(2*n);for(int i 0; i 2*n; i) {arr[i] nums[i % n];}dequeint dq;vectorint result;for(int i 0; i 2*n; i) {// 维护单调递减队列while(!dq.empty() arr[dq.back()] arr[i]) {dq.pop_back();}dq.push_back(i);// 移除超出窗口的元素if(dq.front() i - k) {dq.pop_front();}// 获取窗口最大值if(i k-1) {result.push_back(arr[dq.front()]);}}return result;
}
6.2. 状态压缩
对于某些特殊环形问题可以压缩状态空间
// 环形染色问题
int circleColor(int n) {// dp[i]表示i个位置环形染色的方案数vectorlong dp(n1);dp[1] 3; // 三种颜色dp[2] 6; // 3*2for(int i 3; i n; i) {// 状态转移考虑首尾颜色关系dp[i] dp[i-1] 2 * dp[i-2];}return dp[n];
}
