CSP历年复赛题-P1043 [NOIP2003 普及组] 数字游戏

原题链接：https://www.luogu.com.cn/problem/P1043

题意解读：将n个环形数分成任意m组，组内求和再%10、负数转正，组间相乘，求所有分组方案中得到结果的最小值和最大值。

解题思路：

比赛题的首要目的是上分！此题一看就是DP，但是苦苦思索了半天，想不清楚状态表示，那么可以换换策略，先暴力得分再说！

暴力的思路：

1、对分组方案进行枚举，n个数分成m组，即将n拆解为m个数之和，用DFS搜索所有的方案，存入数组b[]

2、再从环形数组任意位置开始，根据方案数组b[]，依次计算每个组内的和、再%10，各组的结果相乘，更新最大、最小值

3、为了简化环形数组的处理，可以将数组a[n]复制2倍长成a[2n]，从1~n任意位置开始，根据分组方案进行计算即可

4、对于每组数据求和，可以通过前缀和来提速

很惊喜，可以得到80分（比赛中如果此题得到80分也不错了：））

80分代码：

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

const int N = 55, M = 10;
int n, m;
int a[2 * N]; //原数字，扩充2倍长度
int s[2 * N]; //前缀和
int b[M]; //一种分配方案：分成m组，每组几个数
int maxans = INT_MIN;
int minans = INT_MAX;

//给第k组分数，一共还有cnt个数
void dfs(int k, int cnt)
{
    if(k == m) //如果是给最后一组分数
    {
        b[k] = cnt; //剩下的只能全分给最后一组
        //从1~n任意一个作为起点，按照分配方案把n个数共m组进行分别计算
        //每一组求和，%10，各个组相乘，记录最大、最小值
        for(int i = 1; i <= n; i++)
        {
            int start = i; //每一段的起始位置
            int ans = 1;
            for(int j = 1; j <= m; j++)
            {
                int sum = s[start + b[j] - 1] - s[start - 1]; //利用前缀和计算每一段的和
                start += b[j]; //start更新为下一段的起始位置
                sum = (sum % 10 + 10) % 10; //避免sum是负数，取模加10再取模
                ans *= sum;
            }
            maxans = max(maxans, ans);
            minans = min(minans, ans);
        }
        
        return;
    } 
    for(int i = 1; cnt - i >= m - k; i++) //给第k组分数，剩下的个数不能小于剩下的组数
    {
        b[k] = i;
        dfs(k + 1, cnt - i);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i]; //将数字数组加长2倍
    }
    for(int i = 1; i <= 2 * n; i++)
    {
        s[i] = s[i - 1] + a[i]; //计算前缀和
    }

    dfs(1, n);

    cout << minans << endl;
    cout << maxans << endl;

    return 0;
}

进一步思考，该题直观上就是一个区间/环形DP问题，普通的区间问题是最终合并成一段，而此题最终分成m段

因此，状态表示上，需要增加一维，变成三维。主要过程如下：

1、状态表示

a[2 * N]表示原数组，将环拆开成链，增长2倍

s[2 * N]表示前缀和数组，便于快速求一组数据的和

f[i][j][k]表示i ~ j分成k组，所得到的最大值

g[i][j][k]表示i ~ j分成k组，所得到的最小值

2、状态转移

考虑最后一组的位置，设最后一组的起始位置为l，则有

for(int i = 1; i <= n; i++)

  for(int j = i + 1; j < 2 * n; j++)

    for(int k = 2; k <= m; k++)

      for(int l = i+k-1; l <= j; l++) //前面k-1组至少k-1个数，最后一组最大从i+k-1开始

        f[i][j][k] = max(f[i][j][k], f[i][l-1][k-1] * f[l][j][1]) 

        g[i][j][k] = min(g[i][j][k], g[i][l-1][k-1] * g[l][j][1])        

3、初始化

f初始化为0，g初始化为极大值

所有的f[i][j][1] = g[i][j][1] = ((s[j] - s[i-1]) % 10 + 10) % 10

4、结果

最大值：所有>=0的f[i][i+n-1][m]的最大值

最小值：所有>=0的g[i][i+n-1][m]的最小值

100分代码：

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

const int N = 55, M = 10;
int n, m;
int a[2 * N]; //原数字，扩充2倍长度
int s[2 * N]; //前缀和
int f[2 * N][2 * N][M];
int g[2 * N][2 * N][M];
int maxans = 0;
int minans = INT_MAX;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i]; //将数字数组加长2倍
    }
    for(int i = 1; i <= 2 * n; i++)
    {
        s[i] = s[i - 1] + a[i]; //计算前缀和
    }

    memset(g, 0x3f, sizeof(g));

    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j < 2 * n; j++)
        {
             f[i][j][1] = g[i][j][1] = ((s[j] - s[i-1]) % 10 + 10) % 10;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j < 2 * n; j++)
        {
            for(int k = 2; k <= m; k++)
            {
               for(int l = i + k - 1; l <= j; l++) //最后一组的起始位置，预留k-1个数
                {
                    f[i][j][k] = max(f[i][j][k], f[i][l-1][k-1] * f[l][j][1]);
                    g[i][j][k] = min(g[i][j][k], g[i][l-1][k-1] * g[l][j][1]);
                }
            }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(f[i][i+n-1][m] >= 0) maxans = max(maxans, f[i][i+n-1][m]);
        if(g[i][i+n-1][m] >= 0) minans = min(minans, g[i][i+n-1][m]);
    }
    cout << minans << endl;
    cout << maxans << endl;

    return 0;
}