洛谷P1043数字游戏题解--zhengjun

Ophelia ·

更新时间:2024-09-21

· 795 次阅读

题目描述

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共nnn个），你要按顺序将其分为mmm个部分，各部分内的数字相加，相加所得的mmm个结果对101010取模后再相乘，最终得到一个数kkk。游戏的要求是使你所得的k最大或者最小。

例如，对于下面这圈数字（n=4,m=2n=4,m=2n=4,m=2）：

要求最小值时，((2−1) mod 10)×((4+3) mod 10)=1×7=7((2-1) \bmod 10)×((4+3) \bmod 10)=1×7=7((2−1)mod10)×((4+3)mod10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(−1 mod 10)=9×9=81((2+4+3) \bmod 10)×(-1 \bmod 10)=9×9=81((2+4+3)mod10)×(−1mod10)=9×9=81。特别值得注意的是，无论是负数还是正数，对101010取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

输入格式

输入文件第一行有两个整数，n(1≤n≤50)n(1≤n≤50)n(1≤n≤50)和m(1≤m≤9)m(1≤m≤9)m(1≤m≤9)。以下nnn行每行有个整数，其绝对值 ≤104\le 10^4≤104，按顺序给出圈中的数字，首尾相接。

输出格式

输出文件有222行，各包含111个非负整数。第111行是你程序得到的最小值，第222行是最大值。

输入输出样例 输入 #1 复制

输出 #1 复制

7
81

思路

这题是一个典型的区间dp。

为了让一个环变成一条链，就可以把换剪开，在剪开的地方添加剪开前相连的数，然后就是把原数组翻了两倍，这样做dp就可以了，不过还要注意一下最终的答案要重新找一下。

用fi,j,kf_{i,j,k}fi,j,k表示在iii到jjj的区间中分成kkk份所得的最大(最小)值。

转移公式：

fi,j,k=max⁡/min⁡{fi,t,k−1+sumt+1,j mod 10}f_{i,j,k}=\max/\min\{f_{i,t,k-1}+sum_{t+1,j}\bmod10\}fi,j,k=max/min{fi,t,k−1+sumt+1,jmod10}

i+k−2≤t<j,sumi,ji+k-2\leq t<j,sum_{i,j}i+k−2≤t<j,sumi,j表示从iii到jjj段的总和

这个sumsumsum可以用前缀和处理出来

代码

#include
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
int n,m;
int minf[101][101][10],maxf[101][101][10];
int a[101];
int mod(int x){
	return ((x%10)+10)%10;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
    	a[i+n]=a[i];//翻两倍
	}
	for(int i=2;i<=2*n;i++)a[i]+=a[i-1];//前缀和
	for(int i=1;i<=2*n;i++)
	    for(int j=i+1;j<=2*n;j++)
	        for(int k=2;k<=j-i+1;k++)
	            minf[i][j][k]=0x7fffffff;//初始值
	for(int i=1;i<=2*n;i++)
	    for(int j=i;j<=2*n;j++)
	        minf[i][j][1]=maxf[i][j][1]=mod(a[j]-a[i-1]);//不分的时候就是这段的和mod 10
	for(int i=2;i<=m;i++){//枚举分的段数
		for(int j=1;j<=2*n;j++){//枚举左端点
			for(int k=j+i-1;k<=2*n;k++){//枚举右端点
				for(int l=j+i-1-1;l<=k-1;l++){//枚举从哪里切一刀
					minf[j][k][i]=min(minf[j][k][i],minf[j][l][i-1]*mod(a[k]-a[l]));//注意这里的l已经是sum的左端点-1了
					maxf[j][k][i]=max(maxf[j][k][i],maxf[j][l][i-1]*mod(a[k]-a[l]));
				}
			}
		}
	}
	int minans=0x7fffffff,maxans=0;
	for(int i=1;i<=n;i++){//寻找答案
		minans=min(minans,minf[i][i+n-1][m]);
		maxans=max(maxans,maxf[i][i+n-1][m]);
	}
	printf("%d\n%d",minans,maxans);//输出
	return 0;
}

谢谢–zhengjun
作者：A_zjzj

1024 个赞