丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共nn个），你要按顺序将其分为mm个部分，各部分内的数字相加，相加所得的mm个结果对1010取模后再相乘，最终得到一个数kk。游戏的要求是使你所得的k最大或者最小。

例如，对于下面这圈数字（n=4,m=2n=4,m=2）：

要求最小值时，((2-1) \bmod 10)×((4+3) \bmod 10)=1×7=7((2−1)mod10)×((4+3)mod10)=1×7=7，要求最大值时，为((2+4+3) \bmod 10)×(-1 \bmod 10)=9×9=81((2+4+3)mod10)×(−1mod10)=9×9=81。特别值得注意的是，无论是负数还是正数，对1010取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

输入格式

输入文件第一行有两个整数，n(1≤n≤50)n(1≤n≤50)和m(1≤m≤9)m(1≤m≤9)。以下nn行每行有个整数，其绝对值\le 10^4≤104，按顺序给出圈中的数字，首尾相接。

输出格式

输出文件有22行，各包含11个非负整数。第11行是你程序得到的最小值，第22行是最大值。

输入输出样例

输入 #1

4 2
4
3
-1
2

输出 #1

7
81

题意：中文题意。

题目思路：

之前做过一个 划分回文的 划分dp，看到这个题之后没有反应过来，特此总结一下，划分dp

划分dp的基本dp思想：[l,r] 如何划分可以得到最优解，或者[l,r] 划分最少多少次可以满足条件..

基本状态转移

dp[l][r][j]  //代表 l,r 区间内 划分为 J 段的最优贡献

对于此题来说：

其中mod 为取余函数，其余的都是细节问题，比如说由于涉及到乘法，所以边界应该设为1，更简单的我们直接将一段的答案算出来，划分段数从2开始即可。

这题主要是用来总结一下 这个划分dp的思想

AC：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
const ll INF=1e13+7;
ll n,m;
ll num[205];
ll dp1[200][200][20];
ll dp2[200][200][20];
ll sum[205];
ll mod(ll x)
{
    return (x%10+10)%10;
}
void inint()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        num[i+n]=num[i];
    }
    for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+num[i];
}
void work()
{
    //dp1[l][r][j]  i-k 分成 j段获得的最大值
    //dp1[l][r][j] = max dp[l][k][j-1]*(sum[r]-sum[k]);
    for(int l=1;l<=n;l++)
    {
        for(int r=l;r<=l+n-1;r++)//
        {
            dp1[l][r][1]=mod(sum[r]-sum[l-1]);
            dp2[l][r][1]=mod(sum[r]-sum[l-1]);
            for(int j=2;j<=m;j++)
            {
                ll temp1=INF,temp2=-INF;
                for(int k=l;k<r;k++)
                {
                    temp1=min(temp1,dp2[l][k][j-1]*mod(sum[r]-sum[k]));
                    temp2=max(temp2,dp1[l][k][j-1]*mod(sum[r]-sum[k]));
                }
                dp1[l][r][j]=temp2;
                dp2[l][r][j]=temp1;
            }
        }
    }
    ll resmin=INF,resmax=0;
    for(int i=1;i<=n;i++)
    {
        resmax=max(resmax,dp1[i][i+n-1][m]);
        resmin=min(resmin,dp2[i][i+n-1][m]);
    }
    printf("%lld\n%lld\n",resmin,resmax);
}
int main()
{
    inint();
    work();
    return 0;
}

/**

**/