洛谷P1043 [NOIP2003 普及组] 数字游戏

题目链接：P1043 [NOIP2003 普及组] 数字游戏

题意：

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

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

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

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

输入格式：

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

输出格式：

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

显然环形dp，也就是区间dp的升级版。环形dp重点在于断环为链。

一般的处理方式就是把原序列复制一遍，这样选择的最优的起点就是断环的位置。

那么考虑序列的怎么做。设 $f_{i,j,k}$ 表示区间 $[i,j]$ 内分成 $k$ 段的最小值。

转移的话，枚举一个断点 $l$ 并尝试更新，即 $f_{i,l,k-1}\times (S_r - S_l)$ 。其中 $S$ 表示前缀和。

时间复杂度 $\mathcal{O}(n^3m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(115))

int n,m,a[N],F[N][N][12],G[N][N][12];
int Mod(int x) { return (x % 10 + 10) % 10; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) { cin >> a[i]; a[i + n] = a[i]; }
    for(int i = 1; i <= 2 * n; i++) a[i] += a[i - 1];
    for(int l = 1; l <= 2 * n; l++)
        for(int r = l; r <= 2 * n; r++)
            F[l][r][1] = G[l][r][1] = Mod(a[r] - a[l - 1]);
    for(int i = 2; i <= m; i++)
        for(int l = 1; l <= 2 * n; l++)
            for(int r = l + i - 1; r <= 2 * n; r++) F[l][r][i] = INF;
    for(int i = 2; i <= m; i++)
        for(int l = 1; l <= 2 * n; l++)
            for(int r = l + i - 1; r <= 2 * n; r++)
                for(int k = l + i - 2; k < r; k++)
                {
                    up(G[l][r][i], G[l][k][i - 1] * Mod(a[r] - a[k]));
                    down(F[l][r][i], F[l][k][i - 1] * Mod(a[r] - a[k]));
                }
    int mx = 0, mn = INF;
    for(int i = 1; i <= n; i++) {
        down(mn, F[i][i + n - 1][m]); up(mx, G[i][i + n - 1][m]);
    } cout << mn << '\n' << mx << '\n';
    return 0;
}