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

Noah03 · 2025-05-01 15:07:57 · 题解

题意

有一个圆圈，在圆圈上首尾相接的放着 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，表示我们在哪里分割。所以动态转移方程为：

边界条件呢？当 len=1 时，只分成一段，也就是 dp_{i,j,1}=\sum_{k=j}^{i}a_k \ \bmod 10。

代码

下面给出代码。

Code:

//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; //结束
}