P1043 [NOIP 2003 普及组] 数字游戏
#环形结构\#破环成链\#区间DP
这道题是关于一个环上的区间DP问题，n个数字收尾相连成一个环，我们的任务是把n个数分成m个部分，各个部分内的数相加并对10取模再相乘，最后得到一个k值。要求求出k的最大值和最小值。
前置知识
区间DP
DP问题的变种，一种解决涉及连续区间的最优性问题的有效方法。通过求出所有较小区间的最优解，地推出包含它们的较大区间的最优解，具有动态规划的最优子结构和无效性的特性。
状态转移方程如下
dp[i][j]=min or max(dp[i][j],dp[i][q]opdp[q+1][j])
注意整个动态规划的过程中Len=j-i需要从小到大执行
for(len=2 to N)
for(i = 1 to N - Len + 1)
j = i + len - 1
for(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个元素的子序列。
题解代码
#include<bits/stdc++.h> using namespace std; const int N=105,M=15; 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; cin>>n>>m; s[0]=0; for(int i=1;i<=n;i++) { cin>>num[i]; num[i+n]=num[i]; s[i]=s[i-1]+num[i]; } for(int i=1;i<=2*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 k=2;k<=m;k++) { for(int len=k;len<=2 * n;len++) { for(int i=1;i<=2 * n-len+1;i++) { int j=i+len-1; Max[i][j][k]=INT_MIN; Min[i][j][k]=INT_MAX; for(int q=i + k - 2;q<j;q++) { int v=mod10(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 finalmin=INT_MAX,finalmax=INT_MIN; for(int i=1;i<=n;i++) { if(finalmin>Min[i][i+n-1][m]) finalmin=Min[i][i+n-1][m]; if(finalmax<Max[i][i+n-1][m]) { finalmax=Max[i][i+n-1][m]; } } cout<<finalmin<<endl<<finalmax; return 0; }