【题解】数字游戏

佚名 6年前 (2019-05-10) 随笔 296人围观抢沙发百度已收录

题目描述

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　当求最小值时，为（（2-1）mod10）×（（4+3）mod10）=1×7=7，当求最大值时，为（（2+4+3）mod10）×（-1mod10）=9×9=81。特别值得注意的是，无论是负数还是整数，对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。

输入格式

　　第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。

　　以下n行，每行有一个整数，其绝对值不大于104104，按顺序给出圈中的数字，首尾相接。

输出格式

　　两行，各包含一个非负整数。第一行是你的程序得到的最小值，第二行是最大值。

输入样例

4 2

-1

输出样例

题解

　　区间dp模板题，只需要在多开一重状态表示当前分成了几个部分，最后取分成$m$个部分的最优解即可。

#include <iostream>
#include <cstring> 
#define MAXN 51
#define MAXM 10
#define MOD 10 

using namespace std;

int n, m;
int a[MAXN][MAXN];
long long f[MAXN][MAXN][MAXM];
long long ans;

int main()
{
    cin >> n >> m;
    for(register int i = 1, tmp; i <= n; i++)
    {
        cin >> tmp;
        for(register int  j = 1; j <= n; j++)
        {
            for(register int k = 1; k <= n; k++)
            {
                if((j <= i && k >= i) || (j > k && (j <= i || k >= i)))
                {
                    a[j][k] = ((a[j][k] + tmp) % MOD + MOD) % MOD; 
                }
            }
        }
    } 
    memset(f, 127, sizeof f);
    ans = 0xffffffffff;
    for(register int k = 0; k < n; k++)
    {
        for(register int i = 1; i <= n; i++)
        {
            f[i][(i + k - 1) % n + 1][1] = a[i][(i + k - 1) % n + 1];
            for(register int j = 2; j <= min(k + 1, m); j++)
            {
                for(register int l = i; l < i + k; l++)
                {
                    f[i][(i + k - 1) % n + 1][j] = min(
                        f[i][(i + k - 1) % n + 1][j], 
                        f[i][(l - 1) % n + 1][min(l - i + 1, j - 1)] * 
                        f[l % n + 1][(i + k - 1) % n + 1][max(j - (l - i + 1), 1)]);
                }
            }
        }
    } 
    for(register int i = 1; i <= n; i++)
    {
        ans = min(ans, f[i][((i + n - 2) % n + 1)][m]);
    }
    cout << ans << endl;
    memset(f, 0, sizeof f);
    ans = 0;
    for(register int k = 0; k < n; k++)
    {
        for(register int i = 1; i <= n; i++)
        {
            f[i][(i + k - 1) % n + 1][1] = a[i][(i + k - 1) % n + 1];
            for(register int j = 2; j <= min(k + 1, m); j++)
            {
                for(register int l = i; l < i + k; l++)
                {
                    f[i][(i + k - 1) % n + 1][j] = max(
                        f[i][(i + k - 1) % n + 1][j], 
                        f[i][(l - 1) % n + 1][min(l - i + 1, j - 1)] * 
                        f[l % n + 1][(i + k - 1) % n + 1][max(j - (l - i + 1), 1)]);
                        
                }
            }
        }
    } 
    for(register int i = 1; i <= n; i++)
    {
        ans = max(ans, f[i][((i + n - 2) % n + 1)][m]);
    }
    cout << ans;
    return 0;
}