P1043 数字游戏

传送门

一道dp

首先分析发现，给出的是一个环，而要分割这个环是相当麻烦的事情，这里可以暴力枚举一下，枚举开头的情况，再将所有情况算出来的结果进行比对，最终找出最大值的最小值。

前缀和

这里可以使用前缀和，计算得更方便一些，大大提高了效率。

特殊方法

可以将数组存两次，更方便查询与处理。

例： $1,2,3$ -> $1,2,3,1,2,3$

暴力

枚举左右端点，惊进行择优

再将所有的最大值和最小值比对，找到最终结果即可

上代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
#define o_o 0xfffffff 
using namespace std;
int b[101][101][11],c[101][101][11];//区间[l,r]内分成i段的最大/小值 
int n,m; 
int a[101];//a存放前缀和 
int mod(int a) {
    return ((a%10)+10)%10;
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];//在复制一遍，直接接上 
    }
    for (int i=1;i<=2*n;i++)
      a[i]+=a[i-1];//前缀和 
    for (int l=1;l<=2*n;l++)//暴力枚举左右点~初始化 
      for (int r=l;r<=2*n;r++)
        b[l][r][1]=c[l][r][1]=mod(a[r]-a[l-1]);//初始化不分段的状态 
    for (int i=2;i<=m;i++)//暴力枚举左右点~开始寻找 
      for (int l=1;l<=2*n;l++)
        for (int r=l+i-1;r<=2*n;r++)
          c[l][r][i]=o_o;//求最小值时记得把数组初始化为极大值 
    for (int i=2;i<=m;i++)//枚举分段数 
      for (int l=1;l<=2*n;l++)//枚举左端点 
        for (int r=l+i-1;r<=2*n;r++){//枚举右端点 
            for (int k=l+i-2;k<r;k++){//枚举区间断点 注意范围 
                c[l][r][i]=min(c[l][r][i],c[l][k][i-1]*mod(a[r]-a[k]));//dp 找最小值 
                b[l][r][i]=max(b[l][r][i],b[l][k][i-1]*mod(a[r]-a[k]));//dp 找最大值 
          }
        }
    int a_a=0,i_i=o_o;//答案初始化 
    for (int i=1;i<=n;i++){//遍历所有的答案 
        a_a=max(a_a,b[i][i+n-1][m]);//从前往后扫一遍 
        i_i=min(i_i,c[i][i+n-1][m]);//找到真正的最大值与最小值 
    }
    cout<<i_i<<endl<<a_a;//输出 
    return 0;
}