网站建设 js熊岳网站怎么做

网站建设 js,熊岳网站怎么做,湘潭网站建设湘潭振企专业,珠海网站建设q479185700强涵#环形结构\#破环成链\#区间DP这道题是关于一个环上的区间DP问题#xff0c;n个数字收尾相连成一个环#xff0c;我们的任务是把n个数分成m个部分#xff0c;各个部分内的数相加并对10取模再相乘#xff0c;最后得到一个k值。要求求出k的最大值和最小值。前置知识区间DPDP问…#环形结构\#破环成链\#区间DP这道题是关于一个环上的区间DP问题n个数字收尾相连成一个环我们的任务是把n个数分成m个部分各个部分内的数相加并对10取模再相乘最后得到一个k值。要求求出k的最大值和最小值。前置知识区间DPDP问题的变种一种解决涉及连续区间的最优性问题的有效方法。通过求出所有较小区间的最优解地推出包含它们的较大区间的最优解具有动态规划的最优子结构和无效性的特性。状态转移方程如下dp[i][j]min or max(dp[i][j],dp[i][q]opdp[q1][j])注意整个动态规划的过程中Lenj-i需要从小到大执行for(len2 to N)for(i 1 to N - Len 1)j i len - 1for(q i to j - 1)这道题在这个基础上加了一个因素就是我们有k​个区间。状态定义dp[i][j][k]表示将子序列A[i...j]恰好划分成k个连续子序列所得的最优解。核心思想当我们从i开始到j结束切割点为q我们需要从i到q的k-1个区间的最优解推出i到j之间k个区间的最优解。破环成链在算法竞赛中我们会经常遇到环形结构。这类问题会因为首尾相连的特性变得特别复杂。“破环成链”是一种思维技巧和模板化处理这类问题的预处理方法目的是将环形结构转化为我们更容易处理的链式(线性)问题。核心思想复制一份环上的元素接到原序列的末尾形成一个2N的线性序列。类比1000米赛跑一般学校的操场跑道只有400米当我们需要跑1000米时可以将操场变成400米的直线跑道第二圈接到第一圈后面变成800米第三圈的半圈接到后面变成1000米。对于这道题我们只需要复制成2N​即可因为这个长度从环上任意一点开始包含N​个元素的子序列。题解代码#includebits/stdc.h using namespace std; ​ const int N105,M15; long long Max[N][N][M]; long long Min[N][N][M]; long long num[N],s[N]; ​ int mod10(long long val) { int res val % 10; if (res 0) { res 10; // 确保负数取模结果在 [0, 9] } return res; } ​ int main() { int n,m; cinnm; ​ s[0]0; for(int i1;in;i) { cinnum[i]; num[in]num[i]; s[i]s[i-1]num[i]; } for(int i1;i2*n;i) // 循环到 2n { s[i]s[i-1]num[i]; // s[i] 存储 num[1] 到 num[i] 的和 (1-indexed) } for (int i 1; i 2 * n; i) { for (int j i; j 2 * n; j) { int val mod10(s[j] - s[i - 1]); Max[i][j][1] val; Min[i][j][1] val; } } for(int k2;km;k) { for(int lenk;len2 * n;len) { for(int i1;i2 * n-len1;i) { int jilen-1; Max[i][j][k]INT_MIN; Min[i][j][k]INT_MAX; for(int qi k - 2;qj;q) { int vmod10(s[j]-s[q]); Max[i][j][k]max(Max[i][j][k],Max[i][q][k-1]*v); Min[i][j][k]min(Min[i][j][k],Min[i][q][k-1]*v); } } } } long long finalminINT_MAX,finalmaxINT_MIN; for(int i1;in;i) { if(finalminMin[i][in-1][m]) finalminMin[i][in-1][m]; if(finalmaxMax[i][in-1][m]) { finalmaxMax[i][in-1][m]; } } coutfinalminendlfinalmax; return 0; }