WHCSRL 技术网

# 数字游戏（区间DP）

P1043 [NOIP2003 普及组] 数字游戏

f[][][]

f表示最大值或者最小值

``````#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll f;
ll f1;
ll a,b;
int main(){
ll n,m;
cin>>n>>m;
for(int i=1;i<=100;i++){
for(int j=1;j<=100;j++){
for(int k=1;k<=10;k++){
f1[i][j][k]=100000000;
}
}
}
for(int i=1;i<=n;i++) {
cin>>b[i];
a[i]=b[i]+a[i-1];
}
for(int i=n+1;i<=2*n;i++) a[i]=a[i-1]+b[i-n];

for(int i=1;i<=2*n;i++){
for(int j=1;j<=2*n;j++){
f[i][j]=(a[j]-a[i-1]+100000000)%%10;
f1[i][j]=(a[j]-a[i-1]+100000000)%%10;
}
}
for(int i=1;i<=2*n;i++){
for(int j=i+1;j<=2*n;j++){
for(int k=2;k<=m;k++){
for(int l=i;l<j;l++){
f[i][j][k]=max(f[i][j][k],f[i][l][k-1]*f[l+1][j]);
f1[i][j][k]=min(f1[i][j][k],f1[i][l][k-1]*f1[l+1][j]);
}
}
}
}ll maxa=-1;
ll mina=10000000000;
for(int i=1;i<=n;i++){
maxa=max(maxa,f[i][i+n-1][m]);
mina=min(mina,f1[i][i+n-1][m]);
}
cout<<mina<<endl;
cout<<maxa;
return 0;
}
```123456789101112131415161718192021222324252627282930313233343536373839404142434445464748```