描述
给出n个数围成一个环,将其划分成k个部分,每个部分求和再对10取模,最后将每个部分的值相乘,求其最大值与最小值.
描述
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发 觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加， 相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
格式
输入格式
输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。
输出格式
输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。
限制
各个测试点1s
提示
DP！^_^
分析
简单的划分型dp.转移方程:
dp[i][k]=max{dp[j][k-1]*(s[i]-s[j-1])}.
注意:
1.取模.
2.初始化.
#include <bits/stdc++.h>
using namespace std; const int maxn=+,maxk=+,INF=0x7fffffff; int n,K,ans1,ans2;
int s[maxn<<];
int dp1[maxn][maxk],dp2[maxn][maxk]; int num(int x){ return((x%)+)%; }
void solve(){
ans1=INF,ans2=-INF;
for(int q=;q<=n;q++){
for(int i=;i<=n;i++) dp1[i][]=dp2[i][]=num(s[q-+i]-s[q-]);
for(int k=;k<=K;k++)
for(int i=k;i<=n;i++){
dp1[i][k]=INF,dp2[i][k]=-INF;
for(int j=k-;j<i;j++){
dp1[i][k]=min(dp1[i][k],dp1[j][k-]*num(s[q-+i]-s[q-+j]));
dp2[i][k]=max(dp2[i][k],dp2[j][k-]*num(s[q-+i]-s[q-+j]));
}
}
ans1=min(ans1,dp1[n][K]);
ans2=max(ans2,dp2[n][K]);
}
printf("%d\n%d\n",ans1,ans2);
}
void init(){
scanf("%d%d",&n,&K);
for(int i=;i<=n;i++){
int t; scanf("%d",&t);
s[i]=s[i-]+t;
}
for(int i=n+;i<=*n;i++) s[i]=s[n]+s[i-n];
}
int main(){
init();
solve();
return ;
}