P1043 [NOIP2003 普及组] 数字游戏

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

思路：
区间dp，设dpmax/dpmin[i][j][k]表示从序列i->j分成k份的最大/最小值，然后根据递推公式
dpmin[i][j][m] = min(dpmin[i][j][m], dp[i][k][mi]*dp[k+1][j][m-mi]),for ∀mi∈[1,m),k∈[i,j)注意不用取模，因为求出来的就已经是相乘的结果（这里被坑了）。
代码：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=200;
const int M=13;
#define int long long 
int num[N];
int n,m;
int dpmin[N][N][M],dpmax[N][N][M];
int modten(int num)
{
    while(num<0)num+=10;
    return num%10;
}
signed main()
{
    IOS;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>num[i],num[i]=modten(num[i]),num[i+n]=num[i],num[i]+=num[i-1];
    for(int i=n+1;i<=2*n;i++)num[i]+=num[i-1];
    
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*n;j++)
            dpmin[i][j][1]=dpmax[i][j][1]=modten(num[j]-num[i-1]);
            
    
    for(int mi=2;mi<=m;mi++)
    for(int len=mi;len<=n;len++)
    {
        for(int i=1;i<2*n;i++)
        {
            int j=i+len-1;
            if(j>2*n)break;
            for(int k=i;k<j;k++)
            {
                for(int mii=1;mii<mi;mii++)
                {
                    int dp_choice_min=dpmin[i][k][mii]*dpmin[k+1][j][mi-mii];
                    int dp_choice_max=dpmax[i][k][mii]*dpmax[k+1][j][mi-mii];
                    //if(mi!=m)dp_choice_max=modten(dp_choice_max),dp_choice_min=modten(dp_choice_min);
                    if(dpmin[i][j][mi])dpmin[i][j][mi]=min(dpmin[i][j][mi],dp_choice_min);
                    else dpmin[i][j][mi]=dp_choice_min;
                    if(dpmax[i][j][mi])dpmax[i][j][mi]=max(dpmax[i][j][mi],dp_choice_max);
                    else dpmax[i][j][mi]=dp_choice_max;
                }
            }

        }
    }
    int ansmin=INT_MAX,ansmax=0;
    for(int i=1;i<=n;i++)
    {
        ansmin=min(ansmin,dpmin[i][i+n-1][m]);
        ansmax=max(ansmax,dpmax[i][i+n-1][m]);
    }
    cout<<ansmin<<'\n'<<ansmax;

    return 0;
}