这道题以前做过一次但是这次做又卡了一下。。 对环形就拆成链来做 ， 枚举每一个开头。 之后类似区间处理 ，
蛋疼的一点是在 r-l < k 的时候就是 已经不能分成k份了。这时候返回0 不是-1
（神奇的如果把dp数组初始化成0 会TLE
一个点。。 -1的话就能过 ， 因该是n=50 ，m=1时候的数据。。但是具体不知道怎么改了， 之后再研究下）
题目：
描述
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发 觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加， 相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
格式
输入格式
输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。
输出格式
输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。
限制
各个测试点1s
提示
DP！^_^
代码：
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 #define LL long long 5 #define max(a,b) a<b?b:a 6 #define min(a,b) a<b?a:b 7 int n,m; 8 LL num[200]; 9 LL dp[200][200][10]; 10 LL dpmin[200][200][10]; 11 12 LL dfs( int l , int r , int k) 13 { 14 //if(r-l< k ) return -1; 15 LL &d = dp[l][r][k]; 16 if(d !=-1 )return d; 17 if( k == 1) 18 { 19 LL ret = 0; 20 for(int i=l ; i<r;i++) 21 { 22 ret += num[i%n]; 23 } 24 return d = ret%10; 25 } 26 LL ans = 0; 27 for(int x = l+1; x<r;x++) 28 { 29 ans = max(ans, dfs( l,x, 1)*dfs( x,r,k-1) ); 30 } 31 return d = ans; 32 } 33 34 LL dfsmin( int l , int r, int k) 35 { 36 // if( r- l < k ) return -1; 37 38 LL &d = dpmin[l][r][k]; 39 if( d != -1 )return d; 40 if( k==1) 41 { 42 LL ret = 0; 43 for(int i=l;i<r;i++) 44 ret += num[i%n]; 45 return d = ret%10; 46 } 47 48 LL ans = 0x7ffffff; 49 for(int x = l+1; x<r;x++) 50 { 51 ans = min(ans, dfsmin( l,x, 1)*dfsmin( x,r,k-1) ); 52 } 53 return d = ans; 54 } 55 56 int main() 57 { 58 cin>>n>>m; 59 memset(dp,-1,sizeof(dp)); 60 memset(dpmin,-1,sizeof(dp)); 61 for(int i=0;i<n;i++) 62 { 63 cin>>num[i]; 64 num[i]= (num[i]%10+10)%10; 65 } 66 LL big= 0; 67 LL small = 99999999999; 68 for(int s =0 ;s< n;s++) 69 { 70 big = max( big, dfs( s, s+n, m)); 71 small = min( small , dfsmin( s, s+n, m)); 72 } 73 cout<<small<<endl; 74 cout<<big<<endl; 75 return 0; 76 }