南郵OJ 1017積最大

積最大
時間制限(通常/Java) : 
1000 MS/ 3000 MS          実行メモリ制限:65536 KByte
合計コミット:421           テスト合格:206 
試合の説明
今年は国際数学連盟が確定した「2000-世界数学年」であり、わが国の有名な数学者華羅庚氏の生誕90周年にもふさわしい.華羅庚先生の故郷江蘇金壇で、ユニークな数学知能コンテストの活動を組織し、あなたの親友XZも参加することができました.イベントでは、司会者がイベントに参加したすべての選手にこのようなテーマを出しました.
    長さNの数字列が設けられており、K個の乗号を用いてK+1個の部分に分けることを選手に要求し、このK+1個の部分の積を最大にすることができるように分法を見つけた.
    また、司会者は選手が問題の意味を正しく理解できるようにするために、次のような例を挙げた.
数字の列があります:312、 N=3,K=1の場合、以下の2つの分割法があります.
1)  3*12=36
2)  31*2=62
このとき,タイトル要求に合致した結果は,31*2=62であった.
今、あなたの良い友达のXZを助けてプログラムを設計して、正しい答えを求めてください.
入力
入力は2行です.
第1行は2つの自然数N,K(6≦N≦40,1≦K≦6)を有する.
2行目は長さNの数字列です.
しゅつりょく
求めた最大積(自然数)を出力し、答えはlong long データ範囲内.
サンプル入力
4  2 1231
サンプル出力
62
テーマソース
NOIP 2000

#include <iostream>
#include <iomanip>				//cout<<setiosflags(ios::left)<<setw(10)<<m<<endl;
#define MAX(a,b) (a>b?a:b)
using namespace std;

int main(void){
	int N=0,K=0,i=0,j=0,k=0;
	long long num=0;
	long long a[40][40]={0};	//a[i][j]：  i   j       ,i,j∈[0,N-1]
	long long f[40][7]={0};		//f[j][k]：  j     k         ,j∈[1,N],k  [1,K]

	cin>>N>>K>>num;
	for(i=N-1;i>=0;--i){		// a[][]       
		a[i][i] = num%10;
		num /= 10;
	}
	for(i=N-1;i>=0;--i){		// a[][]      
		for(j=i+1;j<N;++j){
			a[i][j] = a[i][j-1]*10+a[j][j];
		}
	}
	/*  a[][]  
	cout<<right;
	for(i=0;i<N;++i){
		for(j=0;j<N;++j){
			cout<<setw(5)<<a[i][j];
		}
		cout<<endl;
	}*/
	for(j=1;j<=N;++j){			//j∈[1,N]
		f[j][0] = a[0][j-1];	//  f[][]   ,       j      
	}
	for(k=1;k<=K;++k){			//    
		for(j=k+1;j<=N;++j){	//  j     k   ，  f[j][k]，j>k,     >    
			for(i=k;i<j;++i){	//i:       i    
				f[j][k] = MAX(f[j][k],f[i][k-1]*a[i][j-1]);	
			}
		}
	}
	/*
	cout<<endl;
	for(i=0;i<=N;++i){
		for(j=0;j<=K;++j){
			cout<<setw(5)<<f[i][j];
		}
		cout<<endl;
	}*/
	cout<<f[N][K]<<endl;
}