Luogu P1043 数字游戏

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

const int maxn = 105;
const int INF = 0x3f3f3f3f;
int n,m;
long long ans1,ans2,a[maxn],f[maxn][maxn][10],g[maxn][maxn][10];

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
        scanf("%lld",&a[i]);
        a[i+n] = a[i];
    }

    for(int t = 1; t <= m; t++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i+n-1; j++)
                g[i][j][t] = INF;

    for(int i = 1; i <= n+n; i++)
        a[i] += a[i-1];
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= i+n-1; j++)
            f[i][j][1] = g[i][j][1] = ((a[j]-a[i-1])%10+10)%10;

    for(int t = 2; t <= m; t++)
        for(int i = 1; i <= n; i++)
            for(int j = i+t-1; j <= i+n-1; j++)
                for(int k = i+(t-1)-1; k < j; k++) {
                    f[i][j][t] = max(f[i][j][t],f[i][k][t-1] * (((a[j]-a[k])%10+10)%10));
                    g[i][j][t] = min(g[i][j][t],g[i][k][t-1] * (((a[j]-a[k])%10+10)%10));
                }

    ans2 = INF;
    for(int i = 1; i <= n; i++) {
        ans1 = max(ans1,f[i][i+n-1][m]);
        ans2 = min(ans2,g[i][i+n-1][m]);
    }
    printf("%lld\n%lld\n",ans2,ans1);
    return 0;
}