?? 最大乘積 動態規劃.txt
字號:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
//最大乘積 動態規劃
#define NMAX 12
#define CMAX 7
__int64 f[NMAX][CMAX];//f[i][j],長度為i,用了j個乘號后的最大值
char str[22];
void print(int num,int k)
{ //用于調試時打印f[][]
int i,j;
for(i=0;i<num;i++)
{
for(j=1;j<=k;j++)
printf("%6d",f[i][j]);
cout<<endl;
}
cout<<endl;
// system("pause");
}
int conv(int start,int num)
{ //在str[i]中,以start為起點,num為長度所表示的數字
int sum,i;
sum=0;
for(i=1;i<=num;i++)
{
sum*=10;
sum+=str[start+i-1]-'0';
}
return sum;
}
void cal(int num,int chen)
{
int i,j,temp,k;
for(i=0;i<num;i++)
{ //初始化,不用乘號時的情況
f[i][0]=conv(0,i+1);
}
for(j=1;j<=chen;j++)
{
for(i=j;i<num;i++)
{
temp=0;
for(k=0;k<i;k++)
{
//a1,a2,a3..an用j個乘號連接
//看成是a1,a2...ak已經用j-1個乘號連接,
//然后再與后面的ak+1,ak+2..an組成的數用1個乘號連接
if(temp<f[k][j-1]*conv(k+1,i-k))
temp=f[k][j-1]*conv(k+1,i-k);
}
f[i][j]=temp;//找到局部的最大乘積
}
// print(num,chen);
}
}
int main()
{
int num,chen;
while(scanf("%d%d",&num,&chen)!=EOF)
{
scanf("%s",&str);
cal(num,chen);
printf("%I64d\n",f[num-1][chen]);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -