[dynamic programming] p1018 linear DP: maximum product

 

Code ：

This problem needs high precision , Only through 20 branch

#include<iostream>
#include<string>
using namespace std; 
int dp[41][6];
int a[41];
int to_int(int i,int j){
	int res=0;
	for(int k=i;k<=j;k++){
		res=res*10+a[k];
	}
	return res;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%1d",&a[i]);// Take only one number at a time 
	}
	for(int i=1;i<=n;i++){
		dp[i][0]=to_int(1,i);
	}
	
	for(int i=1;i<=n;i++){
		for(int k=1;k<=m;k++){
			for(int j=1;j<i;j++){
				if(i<=k)dp[i][k]=0;
				else
				dp[i][k]=max(dp[i][k],dp[j][k-1]*to_int(j+1,i));
			}
		}
	}
	cout<<dp[n][m];


}