题目描述
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共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
- 可以用f[i] [j] [k]表示i到j划分k段的最大值
- 可以考虑出k段是由k-1段转移过来的,然后可以由第k段的长度来划分
- 则f[i] [j] [k]可以由f[i] [x] [k-1] *最后一段的值转移过来
- 最小值同理
- 至于环形首尾的处理,我们可以破环成链
- 时间复杂度 o(N^3m)
#include<iostream>
using namespace std;
const int N = 110;
int a[N];
int f[N][N][11];//f[i][j][m]表示i-j这段分割成m段得到的最大值
int g[N][N][11];//g[i][j][m]表示i-j这段分割成m段得到的最小值
int n,m;
int sum[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
a[n+i]=a[i];
}
for(int i=1;i<=2*n;++i)
sum[i]=a[i]+sum[i-1];
for(int k=1;k<=m;++k){//转移需要前面的,故先处理关于前一的所有信息
for(int len=1;len<=n;++len){
for(int j=1;j<=n;++j){
int l=j,r=j+len-1;
if(k==1){//此时不能划分更小的,就特殊处理
g[l][r][k]=f[l][r][k]=((sum[r]-sum[l-1])%10+10)%10;
}
else{//可以划分为更小的区间
//f[l][r][k] = -1e9;
g[l][r][k] = 1e9;//这个必须,因为值肯定是要大于0的,不然没法更新答案
for(int x=l+k-1;x<=r;++x){//由最后一段的长度来划分
f[l][r][k]=max(f[l][r][k],f[l][x-1][k-1]*(((sum[r]-sum[x-1])%10+10)%10));
g[l][r][k]=min(g[l][r][k],g[l][x-1][k-1]*(((sum[r]-sum[x-1])%10+10)%10));
}
}
}
}
}
int maxv=-1e9,minv=1e9;
for (int i = 1; i <= n; i ++ )
{
maxv = max(maxv, f[i][i + n - 1][m]);
minv = min(minv, g[i][i + n - 1][m]);
}
cout<<minv<<endl<<maxv<<endl;
return 0;
}
请问请问:
for(int x=l+k-1;x<=r;++x){//由最后一段的长度来划分
这里的循环为什么要从l+k-1;
开始呢??嗯,我懂了!!!