code

#include<cstdio> #include<algorithm> #include<cstring> #define oo 2147483647 using namespace std; int B[101][101][11],S[101][101][11]; int n,m; int a[101]; int mod(int a) { return ((a%10)+10)%10; } int main() { scanf("%d %d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; } for (int i=1;i<=2n;i++) a[i]+=a[i-1]; for (int l=1;l<=2n;l++) for (int r=l;r<=2n;r++) B[l][r][1]=S[l][r][1]=mod(a[r]-a[l-1]); for (int i=2;i<=m;i++) for (int l=1;l<=2n;l++) for (int r=l+i-1;r<=2n;r++) S[l][r][i]=oo; for (int i=2;i<=m;i++) for (int l=1;l<=2n;l++) for (int r=l+i-1;r<=2*n;r++) { for (int k=l+i-2;k<r;k++) { S[l][r][i]=min (S[l][r][i],S[l][k][i-1]*mod(a[r]-a[k])); B[l][r][i]=max (B[l][r][i],B[l][k][i-1]*mod(a[r]-a[k])); } } int Max=0,Min=oo; for (int i=1;i<=n;i++) { Max=max(Max,B[i][i+n-1][m]); Min=min(Min,S[i][i+n-1][m]); } printf("%d\n%d",Min,Max); return 0; }

算法 (DP,区间DP)O(n3m)\bold O(\bold n^3\bold m)O(n3m) 首先将环从起点处断开，然后复制一遍接在后面，这样原问题就转化成了线段型的模型。 然后从集合角度来分析状态表示和状态计算： 状态表示： * f[l][r][i]，表示所有将 a[l…r] 分割成 i 部分的方案的最大乘积； * g[l][r][i] ，表示所有将 a[l…r] 分割成 i 部分的方案的最小乘积； * 状态计算： 首先考虑 f[l][r][i] 如何计算，关键是寻找“集合划分的依据”，划分依据一般选取“最后一步的操作”，所以这里我们可以按最后一部分的位置来将 f[l][r][i] 所表示的所有方案划分成若干类： * 最后一段是 a[l + i - 1…r] 的所有划分方案； * 最后一段是 a[l + i…r] 的所有划分方案; ··· * 最后一段是 a[r…r] 的所有划分方案； 如果最后一段是 a[k…r] ，那么这一类的最大值是 f[l][k - 1][i - 1] * sum(a[k…r]) ，其中 sum() 计算某一段数的和模10的余数。 f[l][r][i] 取所有类别的最大值即可。 g[l][r][i] 的计算方式类似。 最终枚举所有长度是n的区间，取最大值/最小值即可。 时间复杂度 状态总共有O(n2m)O(n^2m)O(n2m)计算每个状态需要O(n)O(n)O(n)的计算量，因此总时间复杂度是 O(n3m)O(n^3m)O(n3m) AC代码

1、破环成链。没有太多的技巧性，具体而言就是把数据存储两遍，使得环形的数据可以链式展开，便于我们去DP。 但最后一定要记得扫一遍答案，取F[i][i+N-1]，i：1->N中的最大/小值。 2、前缀和。这个东西并不是在所有情况下都适用，但使用起来真的很方便，可以把O(n)的复杂度优化为O(1)。不过只适用于需要把数据直接相加的地方，比如说这道题。 3、初始化。这里实际上包括两点，一方面是在某些特殊情况下需要初始化，初始化为某特定值（比如本题只分成1段的时候）。另一方面也就是数组初始化，求最大值的时候根本不用管（因为初始默认为0），在求最小值的时候把数组全部赋初值为极大值就好啦。 4、状态表达。一般来说可以用F[i][j]表示在区间[i,j]中怎么怎么样，但由于本题还加了一个分为几段的状态，就把数组直接加一维就好了。

9ms + AC代码

#include<bits/stdc++.h> using namespace std; int n,m; int a[205],s[205]; int f[105][105][15],g[105][105][15]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]=(a[i]%10+10)%10; a[n+i]=a[i]; } int N=2n; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { for(int k=0;k<=m;k++) { f[i][j][k]=100000000; } } } for(int i=1;i<=N;i++) { s[i]=s[i-1]+a[i]; } for(int i=1;i<=N;i++) { for(int j=i;j<=N;j++) { f[i][j][1]=(s[j]-s[i-1])%10; g[i][j][1]=(s[j]-s[i-1])%10; } } for(int l=2;l<=m;l++) { for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=N;i++) { int j=i+len-1; for(int k=i;k<j;k++) { f[i][j][l]=min(f[i][j][l],f[i][k][l-1]((s[j]-s[k])%10)); g[i][j][l]=max(g[i][j][l],g[i][k][l-1]*((s[j]-s[k])%10)); } } } } int minans=0x3f3f3f3f; int maxans=0; for(int i=1;i<=n;i++) { minans=min(minans,f[i][i+n-1][m]); maxans=max(maxans,g[i][i+n-1][m]); } cout<<minans<<endl<<maxans; return 0; }