[NOIP2003 普及组] 数字游戏

题目描述

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共 \(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\) 取模的结果均为非负值。

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

4 2
4
3
-1
2

样例输出 #1

7
81

提示

【题目来源】

NOIP 2003 普及组第二题

思路

我们先破环成链
我们显然要维护一个区间 再维护一个分k个部分
这样我们的状态转移方程就出来了
dp[i][j][k]表示开头为ai 结尾为aj 并且分成了 k段
dp[i][j][k]=min/max{dp[i][r][k-1]+mod(s[j]-s[r])}
但是显然我们从k=1枚举 那显然不好规定 k=0的值
所以我们初始化k=1 k从2开始枚举
最后就是断点的枚举范围
首先我们知道其只分为了k-1段
那我们肯定大于等于i+k-2 小于j 因为等于j就没变
以前都没注意这些合法性 这次吃瘪了捏

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[110][110][10];//i开头 到j 划分了k段 且结尾是aj
void solve() {
    int n,m;cin>>n>>m;
    vector<int>a(n+1),s(n*2+1);
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
    for(int i=n+1;i<=n<<1;i++)s[i]=s[i-1]+a[i-n];
    memset(dp,0x3f3f,sizeof dp);
    for (int l=1;l<=2*n;l++)
        for (int r=l;r<=2*n;r++)
            dp[l][r][1]=(((s[r]-s[l-1])%10+10)%10);
    for(int i=2;i<=m;i++)
        for(int l=1;l<=n;l++)
            for(int r=l+i-1;r<l+n;r++)
                for(int k=l+i-2;k<r;k++)
                    dp[l][r][i]=min(dp[l][r][i],dp[l][k][i-1]*(((s[r]-s[k])%10+10)%10));
    int mn=INF;
    for(int i=1;i<=n;i++)mn=min(mn,dp[i][i+n-1][m]);
    cout<<mn<<endl;
    memset(dp,0,sizeof dp);
    for (int l=1;l<=2*n;l++)
        for (int r=l;r<=2*n;r++)
            dp[l][r][1]=(((s[r]-s[l-1])%10+10)%10);
    for(int i=2;i<=m;i++)
        for(int l=1;l<=n;l++)
            for(int r=l+i-1;r<l+n;r++)
                for(int k=l+i-2;k<r;k++)
                    dp[l][r][i]=max(dp[l][r][i],dp[l][k][i-1]*(((s[r]-s[k])%10+10)%10));
    int mx=0;
    for(int i=1;i<=n;i++)mx=max(mx,dp[i][i+n-1][m]);
    cout<<mx<<endl;
}
signed main(){
    fast
    int T;T=1;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}