1085 数字游戏  2003年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解题目描述 Description丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如，对于下面这圈数字（n=4，m=2）：                                  2                   4                           -1                                 3当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。输入描述 Input Description输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。输出描述 Output Description输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。样例输入 Sample Input4 243-12样例输出 Sample Output781数据范围及提示 Data Size & Hinten分类标签 Tags 点此展开 划分型DP 动态规划 环型DP NOIP全国联赛普及组 大陆地区 2003年

#include<iostream>#include<cstring>using namespace std;int n,m;int minl=0x3f3f,maxl=-999;int fmax[205][205][10],fmin[205][205][15];int s[1000];int mod(int i){    if(i>0)return i%10;    else return (i%10+10)%10;}int main(){    cin>>n>>m;    for(int i=1;i<=200;i++)        for(int j=1;j<=200;++j)            for(int k=1;k<10;++k)                fmin[i][j][k]=1000;    for(int i=1;i<=n;++i)    {        cin>>s[i];        s[i+n]=s[i];    }    for(int i=2;i<=n*2;++i)        s[i]=s[i-1]+s[i];    for(int i=1;i<=2*n;++i)        for(int j=1;j<=2*n;++j)            fmin[i][j][1]=fmax[i][j][1]=mod(s[j]-s[i]);    for(int l=2;l<=m;++l)        for(int i=1;i<=n;++i)            for(int j=i;j<=2*n;++j)                for(int k=i+1;k<j;++k)                {                    fmax[i][j][l]=max(fmax[i][j][l],fmax[i][k][l-1]*fmax[k][j][1]);                    fmin[i][j][l]=min(fmin[i][j][l],fmin[i][k][l-1]*fmin[k][j][1]);                }    for(int i=1;i<=n;++i)    {        minl=min(minl,fmin[i][i+n][m]);        maxl=max(maxl,fmax[i][i+n][m]);    }        cout<<minl<<endl;    cout<<maxl<<endl;}