P1043 数字游戏 • CoderXL's Blog

先考虑在线性区间上的问题，环的情况稍后可以很容易地转换到线性区间上。

像这种区间划分的问题，我们经常要思考一件问题：两个（或若干个）子区间的答案能否拼成更大区间的答案。

如果可以，那么我们不需要暴力地枚举区间分段点（暴力是 $O(C_{n}^m)$ 的），而只需要把从短到长的每个区间（这样的区间有 $O(n^2)$ 个）的答案依次算出来并进行转移即可。

具体到这道题，我们考虑设计一个状态 $dp[l][r][s]$ ，表示区间 $[l,r]$ 被划分成 $s$ 段时，子问题的答案。题目要求两个问题：乘积的最小值和最大值。因此我们用两个数组 $dpl$ 和 $dph$ （即 lowest 和 highest）。

状态转移比较显然：先从小到大枚举区间长度 $len$ ，然后枚举区间左端点 $l$ 并记 $r \triangleq l+len-1$ ，再枚举划分的段数 $s$ ，然后考虑： $dp[l][r][s]$ 表示区间 $[l,r]$ 被划分成 $s$ 段时的答案，那么最后一段的左端点必然在中间某处 $k \in [l,r]$ ，于是可以答案可以从 $dp[l][k-1][s-1]\times dp[k][r][1]$ 转移过来。因此最内层要枚举 $k$ ，并令 $dph[l][r][s]=\max_k dph[l][k-1][s-1]\times dph[k][r][1]$ ， $dpl$ 同理。

时间复杂度 $O(n^3m)$ ，空间复杂度 $O(n^2m)$ .

此外，我们发现对于每个 $s$ ，我们只需要知道 $dp$ 数组在 $[\cdot][\cdot][1]$ 和 $[\cdot][\cdot][s-1]$ 的值，因此可以通过把 $s$ 的枚举转换到最外层并使用滚动数组，进一步把空间复杂度降低到 $O(n^2)$ .

[!hint] 对于本题， $m\le 9$ 确实没有必要。

如何处理环？我发现，无非就是让线性区间向左右延伸，超出边界的位置回到开头。为此，我们只需要把环断开成线性区间，然后复制一份，接在后面。在这个两倍长的线性区间上按照之前的方法进行区间 DP。然后由于环的旋转对称性，“起点”可能在 $1\sim n$ 中的任何一点，于是遍历 $k \in [1,n]$ ，取 $\max_k dph[k][k+n-1][m]$ 和 $\min_k dph[k][k+n-1][m]$ .

#include <bits/stdc++.h>
using namespace std;

const int N = 60, M = 10, MOD = 10;

using ll=long long;

int n,m;

ll dpl[M][N][N],dph[M][N][N];//lowest highest
int a[N];
ll ansl=LLONG_MAX,ansh;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int k=2;k<=m;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
        dpl[k][i][j]=INT_MAX;
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            dpl[1][i][j]=dpl[1][i][(j-1+n)%n]+a[j];
            dph[1][i][j]=dph[1][i][(j-1+n)%n]+a[j];
        }
        for(int j=0;j<i;j++)
        {
            dpl[1][i][j]=dpl[1][i][(j-1+n)%n]+a[j];
            dph[1][i][j]=dph[1][i][(j-1+n)%n]+a[j];
        }
        for(int j=0;j<n;j++)
        {
            dpl[1][i][j]=(dpl[1][i][j]%MOD+MOD)%MOD;
            dph[1][i][j]=(dph[1][i][j]%MOD+MOD)%MOD;
        }
    }
    for(int k=2;k<=m;k++)
    {
        for(int l=k;l<=n;l++)//length of the section
        {
            for(int i=0,j;i<n;i++)//the left end of the section
            {
                j=(i+l-1)%n;
                for(int d=i;d!=j;d=(d+1)%n)
                {
                    dph[k][i][j]=max(dph[k][i][j],dph[k-1][i][d]*dph[1][(d+1)%n][j]);
                    dpl[k][i][j]=min(dpl[k][i][j],dpl[k-1][i][d]*dpl[1][(d+1)%n][j]);
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        ansl=min(ansl,dpl[m][i][(i+n-1)%n]);
        ansh=max(ansh,dph[m][i][(i+n-1)%n]);
    }
    cout<<ansl<<'\n'<<ansh;
    return 0;
}

cpp