石家庄建设厅网站首页,太原seo报价,新兴县城乡建设局网站登录,我的个人网站 的网页设计将n(1≤n≤200)堆石子绕圆形操场摆放#xff0c;现要将石子有次序地合并成一堆。 规定每次只能选相邻的两堆石子合并成新的一堆#xff0c;并将新的一堆的石子数#xff0c;记为该次合并的得分。 (1)选择一种合并石子的方案#xff0c;使得做n-1次合并#xff0c;得分的总…将n(1≤n≤200)堆石子绕圆形操场摆放现要将石子有次序地合并成一堆。 规定每次只能选相邻的两堆石子合并成新的一堆并将新的一堆的石子数记为该次合并的得分。 (1)选择一种合并石子的方案使得做n-1次合并得分的总和最小。 (2)选择一种合并石子的方案使得做n-1次合并得分的总和最大 输入 4 4 5 9 4 输出 43 54
线性结构是N个数据元素以有序的方式排列。访问线性结构一般采用由前至后的遍历方法。 线性动态规划就是在线性数据的基础上通过某种递推方式状态转移方程得到最终结构的一种规划算法。 sum[i]: 从第1堆到第i堆石子数总和 fmax[i][j]: 从第i堆石子合并到第j堆石子的最大得分 fmin[i][j]: 从第i堆石子合并到第j堆石子的最小得分
初始化 fmax[i][i] 0, fmin[i][i] INF 状态方程 fmax[i][j] max{fmax[i][k]fmax[k1][j]sum[j]-sum[i-1]} i k j fmin[i][j] min{fmin[i][k]fmin[k1][j]sum[j]-sum[i-1]} i k j
由于题中围成一个环我们将这条链再延长一倍变成2*n堆地中第i堆与第ni堆相同 动态规划求解后答案为f(1,n), f(2,n1), ... , f(n-1,2*n-2)中的最优解
状态转移 要计算f(i,j)的值时需知道所有f(i,k)和f(k1,j)的值 以lenj-i1作为DP 的区间长度从小到大枚举len 然后枚举i的值根据len和i用公式计算出j的值然后枚举k时间复杂度为O(n^3)
/* https://loj.ac/problem/10147 */ #include iostream using namespace std;
const int MAXN 201; const int INF 0x3f3f3f3f; int arr[2*MAXN]; int sum[2*MAXN]; int fmax[2*MAXN][2*MAXN]; int fmin[2*MAXN][2*MAXN];
int main() { int i, j, k, n, len; cin n; for (i 1; i n; i) { cin arr[i]; arr[ni] arr[i]; } for (i 1; i (n1); i) sum[i] sum[i-1] arr[i]; for (len 2; len n; len) for (i 1; i (n1)-len1; i) { j i len - 1; // 初始化 fmax[i][j] 0; fmin[i][j] INF; for (k i; k j; k) { fmax[i][j] max(fmax[i][j], fmax[i][k] fmax[k1][j] sum[j] - sum[i-1]); fmin[i][j] min(fmin[i][j], fmin[i][k] fmin[k1][j] sum[j] - sum[i-1]); } } int ansmax 0, ansmin INF; for (i 1; i n; i) { ansmax max(ansmax, fmax[i][in-1]); ansmin min(ansmin, fmin[i][in-1]); } cout ansmin endl ansmax endl; return 0; } 四边形不等式优化请参考
https://oi-wiki.org/dp/opt/quadrangle/
https://www.cnblogs.com/a1b3c7d9/p/10984353.html
dp[i][j]min{dp[i][k]dp[k1][j]w[i][j]} (i≤kj) 把dp[i][k]dp[k1][j]取得最值的那个k, 称为dp[i][j]的最优决策点。 #include iostream using namespace std; const int MAXN 201; const int INF 0x3f3f3f3f; int arr[2*MAXN]; int sum[2*MAXN]; int fmax[2*MAXN][2*MAXN]; int fmin[2*MAXN][2*MAXN]; int ma[2*MAXN][2*MAXN]; //ma[i][j] 从第i堆石子合并到第j堆石子的最大得分时的最优决策点 int mi[2*MAXN][2*MAXN]; //mi[i][j] 从第i堆石子合并到第j堆石子的最小得分时的最优决策点
int main() { int i, j, k, n, len, t; cin n; for (i 1; i n; i) { cin arr[i]; arr[ni] arr[i]; } for (i 1; i (n1); i) { sum[i] sum[i-1] arr[i]; ma[i][i] i; mi[i][i] i; } for (len 2; len n; len) for (i 1; i (n1)-len1; i) { j i len - 1; // 初始化 fmax[i][j] 0; fmin[i][j] INF; // 四边形不等式优化 for (k ma[i][j-1]; k ma[i1][j] k j; k) { t fmax[i][k] fmax[k1][j] sum[j] - sum[i-1]; if (fmax[i][j] t) { fmax[i][j] t; ma[i][j] k; } } for (k mi[i][j-1]; k mi[i1][j] k j; k) { t fmin[i][k] fmin[k1][j] sum[j] - sum[i-1]; if (fmin[i][j] t) { fmin[i][j] t; mi[i][j] k; } } } int ansmax 0, ansmin INF; for (i 1; i n; i) { ansmax max(ansmax, fmax[i][in-1]); ansmin min(ansmin, fmin[i][in-1]); } cout ansmin endl ansmax endl; return 0; }
