WHCSRL 技术网

数字游戏(区间DP)

P1043 [NOIP2003 普及组] 数字游戏

f[][][]
第一维第二维表示 第i个到第j个数
第三维表示 i到j 分成几段
f表示最大值或者最小值
四层循环 第一层i
第二层j
第三层分多少段
第四层中间值

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll f[102][102][102];
ll f1[102][102][102];
ll a[10000],b[10000];
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][1]=(a[j]-a[i-1]+100000000)%%10;
			f1[i][j][1]=(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][1]);
					f1[i][j][k]=min(f1[i][j][k],f1[i][l][k-1]*f1[l+1][j][1]);
				}
			}
		}
	}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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
推荐阅读