一 原始数据处理

1.输入数据得到a[1]~a[n],复制扩展a[n+1]~a[2*n]，以便处理不同点为起点出发。

cin>>n>>m;

for(int i=1;i<=n;i++)

{

    scanf("%d",&a[i]);

    a[i+n]=a[i];

}

2.计算前缀和

sum[1]=a[1];

for(int i=2;i<=2*n;i++) sum[i]=sum[i-1]+a[i];

3.除余计算函数

int mod10(int k)

{

    return (k%10+10)%10;

}

二 dp数组定义及转移方程

1 dp定义

dpma [i][j][m] 表示i为起点j为终点，划分m份的最大值；

dpmi [i][j][m] 表示i为起点j为终点，划分m份的最小值；

2 根据定义初始化

dpma [i][j][1];

dpmi [i][j][1];

for(int i=1;i<=2*n;i++)

{

    for (int j=i;j<=2*n;j++)

    {

        dpmi[i][j][1]=dpma[i][j][1]=mod10(sum[j]-sum[i-1]);

        for(int len=2;len<=m;len++)

        {

            dpmi[i][j][len]=2e9;

            dpma[i][j][len]=0;

        }

    }

}

3转移方程：

dpma[i][j][len]=max(1ll*dpma[i][mid][num]*dpma[mid+1][j][len-num],1ll*dpma[i][j][len]));

dpmi[i][j][len]=min(1ll*dpmi[i][mid][num]*dpmi[mid+1][j][len-num],1ll*dpmi[i][j][len]));

len 范围[2,m],最外层循环,用来遍历所有分的份数（因为份数为1的都已初始化）

num是分堆数量取值范围[1,len-1]，用来遍历len堆的方法，len=5，那么num可分成1,4;2,3;3,2;4,1;

i的范围[1,2*n],j的范围[i,2*n],用来遍历起始点。

mid为i~j之间的划分点 ，mid 取值范围[i,j-1]

举例说明mid的必要性，样例a[]={2,-1,3,4},

求dp[1][3][2],

存在{2}，{-1，3}和{2，-1}，{3}按照划mid分点不同存在两种情况，

应比较dp[1][1][1]*dp[2][3][1]和dp[1][2][1]*dp[3][3][1]两者取大

防止dpmi超int界，乘1ll转化为长整型

4 求最大最小值

int maxans=0,minans=2e9;

for(int i=1;i<=n;i++)

{

    maxans=max(dpma[i][i+n-1][m],maxans);

    minans=min(dpmi[i][i+n-1][m],minans);

}

 1 #include<bits/stdc++.h>

 2 #define LL long long

 3 using namespace std;

 4 int dpmi[200][200][200],dpma[200][200][200]={0};

 5 int n,m,a[200]={0},sum[200]={0};

 6 int mod10(int n)

 7 {

 8     return (n%10+10)%10;

 9 }

10

11 int main()

12 {

13 //    freopen("1.in","r",stdin);

14 //    freopen("1.out","w",stdout);

15     cin>>n>>m;

16     for(int i=1;i<=n;i++)

17     {

18         scanf("%d",&a[i]);

19         a[i+n]=a[i];

20     }

21

22     sum[1]=a[1];

23     for(int i=2;i<=2*n;i++) sum[i]=sum[i-1]+a[i];

24

25     for(int i=1;i<=2*n;i++)

26     {

27         for(int j=i;j<=2*n;j++)

28         {

29             dpmi[i][j][1]=dpma[i][j][1]=mod10(sum[j]-sum[i-1]);

30             for(int len=2;len<=m;len++)

31             {

32                 dpmi[i][j][len]=2e9;

33                 dpma[i][j][len]=-1;

34             }

35         }

36     }

37

38

39     for(int len=2;len<=m;len++)

40     {

41         for(int num=1;num<len;num++)

42         {

43             for(int i=1;i<=2*n;i++)

44             {

45                 for(int j=i;j<=2*n;j++)

46                 {

47                     for(int mid=i;mid<=j-1;mid++)

48                     {

49                         dpma[i][j][len]=max(1ll*dpma[i][mid][num]*dpma[mid+1][j][len-num],1ll*dpma[i][j][len]);

50                         dpmi[i][j][len]=min(1ll*dpmi[i][mid][num]*dpmi[mid+1][j][len-num],1ll*dpmi[i][j][len]);

51                     }

52                 }

53             }

54         }

55     }

56     int maxans=-1000,minans=2e9;

57     for(int i=1;i<=n;i++)

58     {

59         maxans=max(dpma[i][i+n-1][m],maxans);

60         minans=min(dpmi[i][i+n-1][m],minans);

61     }

62     printf("%d\n%d",minans,maxans);

63     return 0;

64 }