题目描述

　丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
　　例如，对于下面这圈数字（n=4，m=2）：
　　
当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。

输入

输入第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。

输出

输出有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值

思路

剖分问题，和乘积最大类似
http://blog.csdn.net/nidhogg__/article/details/52642084
只是将这一个环展开，然后枚举起点的位置
注意题目要求不为0，所以每次要加上一个很大的10的倍数然后在mod10

#include 
#include 
using namespace std;
int f[5000][5000],a[5000],b[5000];
int n,m,k;
__attribute__((optimize("O2")))
int max(int x,int y)
{
    return x>y?x:y;
}
__attribute__((optimize("O2")))
int min(int x,int y)
{
    return x=s;l--)
                    f[j][s]=min(f[j][s],f[l][s-1]*xx(l+1,j));
           }
        minl=min(minl,f[n][k]);
    }       
    printf("%d\n",minl);


    for (int o=1;o<=n;o++)
    {
        for (int i=1;i<=n;i++)
            a[i]=b[i+o-1];
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                f[i][j]=-100000000;
            for (int i=2;i<=n-k+1;i++)
        {
            for (int j=1;j<=i-1;j++)
                f[i][1]=max(f[i][1],xx(1,j)*xx(j+1,i));

        }
        for (int s=2;s<=k;s++)
            for (int j=s;j<=n-k+s;j++)
            {
                for (int l=j-1;l>=s;l--)
                    f[j][s]=max(f[j][s],f[l][s-1]*xx(l+1,j));
           }
        maxl=max(maxl,f[n][k]);
    }
    printf("%d\n",maxl);
    return 0;
}