环形dp
模板,代码里面有注解可以配合着看
#include<iostream>
#include<cstring>
using namespace std;
const int N=110,M=11;
const int INF=0x3f3f3f3f;
int f[N][N][M],g[N][N][M]; //存最大值和最小值
//f(g)[l][r][k]表示在l~r的区间内,分割成k部分时的最大(小)值
int s[N],w[N];
int get(int x)
{
return (x%10+10)%10; //返回x%10的正数值
}
int main()
{
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>w[i];
w[i+n]=w[i];
}
for(int i=1;i<=n*2;i++) s[i]=s[i-1]+w[i];
memset(f,-0x3f,sizeof f);
memset(g, 0x3f,sizeof g);
//环形dp
for(int len=1;len<=n;len++)
for(int l=1;l+len-1<=n*2;l++)
{
int r=l+len-1;
//cout<<l<<' '<<r<<':'<<endl;
f[l][r][1]=g[l][r][1]=get(s[r]-s[l-1]); //当序列只有一个部分组成,那么直接求和所有元素
for(int k=2;k<=m;k++) //枚举三维部分个数
{
for(int j=l+k-2;j<r;j++)
{
//前半部分是k-1个部分,枚举最后一个部分的起始位置并做乘法
f[l][r][k]=max(f[l][r][k],f[l][j][k-1]*get(s[r]-s[j]));
g[l][r][k]=min(g[l][r][k],g[l][j][k-1]*get(s[r]-s[j]));
}
//cout<<f[l][r][k]<<' '<<g[l][r][k]<<endl;
}
}
int imin=INF,imax=-INF;
for(int i=1;i<=n;i++)
{
imax=max(imax,f[i][i+n-1][m]);
imin=min(imin,g[i][i+n-1][m]);
}
cout<<imin<<endl<<imax;
return 0;
}
这层的循环为什么
j
从l+k-2开始循环前面的数的个数必须有 l + k - 2 个这样才能保证 至少能被分成 k- 1段;