?? 最大乘積 動(dòng)態(tài)規(guī)劃.txt
字號(hào):
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
//最大乘積 動(dòng)態(tài)規(guī)劃
#define NMAX 12
#define CMAX 7
__int64 f[NMAX][CMAX];//f[i][j],長(zhǎng)度為i,用了j個(gè)乘號(hào)后的最大值
char str[22];
void print(int num,int k)
{ //用于調(diào)試時(shí)打印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為起點(diǎn),num為長(zhǎng)度所表示的數(shù)字
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++)
{ //初始化,不用乘號(hào)時(shí)的情況
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個(gè)乘號(hào)連接
//看成是a1,a2...ak已經(jīng)用j-1個(gè)乘號(hào)連接,
//然后再與后面的ak+1,ak+2..an組成的數(shù)用1個(gè)乘號(hào)連接
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;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -