P1043 [NOIP 2003 普及组] 数字游戏 C++题解

题意

有一个圆圈，在圆圈上首尾相接的放着

n

个数，现在让你按顺序将这些数分成

m

个部分，把每个部分内的数字相加，将这

m

个结果相乘并模

10

，得到最终结果

k

，现在给你

n,m

和

n

个整数，求最大和最小的

k

。

分析

看到题目，先想到了 DFS，但是对于题目的数据范围会直接爆炸。可以使用动态规划，DP 的方法来做这道题。

但是题目中的数字是一条环，怎么办呢？我们可以把这条环拉直，形成一条长为

2 \times n

的链。那我们令

dp_{i,j,len}

为从第

i

个数开始，第

j

个数结束，分成了

len

段。当然，结合题目要求，我们把

dp

数组拆成

Max

数组和

Min

数组（

Max

表示最大，

Min

表示最小）。我们在枚举

i,j,len

后还要枚举一个变量

k

，表示我们在哪里分割。所以动态转移方程为：

Min_{i,j,len}=\min\{Min_{i,j,len},Min_{i,k,len-1} \times Min_{k+1,j,1}\}

边界条件呢？当

len=1

时，只分成一段，也就是

dp_{i,j,1}=\sum_{k=j}^{i}a_k \ \bmod 10

。

代码

下面给出代码。

Code:

CPP

//The Code is From @Noah03(Luogu User Name),Do Not Copy!!!
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[60],s[110],Max[110][110][15],Min[110][110][15];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i]; //前缀和
	}
	for(int i=n+1;i<=(n<<1);i++) s[i]=s[i-1]+a[i-n]; //化环为链
	for(int i=1;i<=110;i++) for(int j=1;j<=110;j++) for(int k=1;k<=10;k++) Min[i][j][k]=1e12; //初始化 
	for(int i=1;i<=(n<<1);i++)
		for(int j=1;j<=(n<<1);j++)
			Max[i][j][1]=Min[i][j][1]=(s[j]-s[i-1]+1000000000)%10;
    //负数取模可能会出现负数，先加上一个极大值
	for(int i=1;i<=(n<<1);i++)
		for(int j=i+1;j<=(n<<1);j++)
			for(int len=2;len<=m;len++)
				for(int k=i;k<j;k++){
					Max[i][j][len]=max(
					Max[i][j][len],
					Max[i][k][len-1]*
					Max[k+1][j][1]);
					Min[i][j][len]=min(
					Min[i][j][len],
					Min[i][k][len-1]*
					Min[k+1][j][1]);
                    //动态转移方程
				}
	ll ans1=0,ans2=1e18;
	for(int i=1;i<=n;i++){
		ans1=max(ans1,Max[i][i+n-1][m]); //取最大值
		ans2=min(ans2,Min[i][i+n-1][m]); //取最小值
	}
	printf("%lld\n%lld\n",ans2,ans1);
	return 0; //结束
}

P1043 [NOIP 2003 普及组] 数字游戏 C++题解

文章操作

题意

分析

代码

相关推荐

评论

P1043 [NOIP 2003 普及组] 数字游戏 C++题解