题解 P1043 【数字游戏】

· · 题解

一看到这道题，我感觉是个深搜

但我们看一数据大量，也就循环个5000亿次而已，于是果断放弃

我们决定用DP，不要问为什么，因为我们可以从几个已知数据得出未知数据

这里要注意了，因为题目中数字构成一个环，所以我们要先化环为链

我们看看我们怎样DP，我们需要一个三维数组f[i][j][l]，i和j表示我们取第i个数字到第j个数字，l表示我们将第i个数字到第j个数字分为l段（f存最大值）

我们明白了动态规划中数组的含义，就能较容易的推出动态规划转移方程了

我们用一个4重循环，第1,2重i,j表示第i个数字到第j个数字，l表示我们将第i个数字到第j个数字分为l段，k表示我们在i,j中取得中间值，将第i个数字到第j个数字拆成第i个数字到第k个数字和第k+1个数字到第j个数字。

明白了动态规划中数组的含义和动态规划转移方程，我们只需要进行一个初始化就行了，通过动态规划转移方程，我们发现无法推出f[i][j][1]，所以我们要做的就是在动归开始前，将全部f[i][j][1]赋值

至于f[i][j][1]的初始值怎么赋，就是枚举i,j，再将第i个数字到第j个数字全部加起 mod 10 就行了

代码附上

#include<iostream>
using namespace std;
long long a[1001],x[1001],n,m,max1,min1=1000000000000000;
//x为一开始读入的数据，a为便于计算一段之和的前缀和 
long long f[101][101][11],f1[101][101][11]; 
//f数组存最大值，f1数组存最小值 
int main(){
    cin>>n>>m;
    for (int i=1;i<=100;i++)
        for (int j=1;j<=100;j++)
            for (int k=1;k<=10;k++)
                f1[i][j][k]=10000000000;
    //先给f1数组赋上巨大的值，便于计算之和的最小值 
    for (int i=1;i<=n;i++)
    {
        cin>>x[i];//读入 
        a[i]+=a[i-1]+x[i];//前缀和 
    }
    //化环为链 
    for (int i=n+1;i<=n*2;i++) a[i]+=a[i-1]+x[i-n];//前缀和 
    for (int i=1;i<=n*2;i++)
        for (int j=1;j<=n*2;j++)
        {
            f[i][j][1]=(a[j]-a[i-1]+100000000000)%10;//前缀和求一段数的和 
            f1[i][j][1]=(a[j]-a[i-1]+100000000000)%10;//前缀和求一段数的和 
            //因为输入有负数，所以a[j]可能会小于a[i-1],所以我们给他加上巨大值 
        }
    //赋初始值  
    for (int i=1;i<=n*2;i++)//枚举开始的数字位置 
    {
        for (int j=i+1;j<=n*2;j++)//枚举结束的数字位置 
        {
            for (int l=2;l<=m;l++)//枚举分段的数量 
            {
                for (int k=i;k<j;k++)//枚举中间数的位置 
                {
                    f[i][j][l]=max(f[i][j][l],f[i][k][l-1]*f[k+1][j][1]);//动态规划转移方程
                    f1[i][j][l]=min(f1[i][j][l],f1[i][k][l-1]*f1[k+1][j][1]);//动态规划转移方程 
                }
            }
        }
    }
    for (int i=1;i<=n;i++) 
    {
        max1=max(max1,f[i][i+n-1][m]);//求一段的最大值 
        min1=min(min1,f1[i][i+n-1][m]);//求一段的最小值  
    }
    cout<<min1<<endl<<max1<<endl;//输出
    return 0; 
}