C說話應用DP靜態計劃思惟解最年夜K乘積與乘積最年夜成績。本站提示廣大學習愛好者：（C說話應用DP靜態計劃思惟解最年夜K乘積與乘積最年夜成績）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話應用DP靜態計劃思惟解最年夜K乘積與乘積最年夜成績正文
最年夜K乘積成績
設I是一個n位十進制整數。假如將I劃分為k段，則可獲得k個整數。這k個整數的乘積稱為I的一個k乘積。試設計一個算法，關於給定的I和k，求出I的最年夜k乘積。
編程義務：
關於給定的I 和k，編程盤算I 的最年夜k 乘積。
需求輸出：
輸出的第1 行中有2個正整數n和k。正整數n是序列的長度；正整數k是朋分的段數。接上去的一行中是一個n位十進制整數。（n<=10）
需求輸入：
盤算出的最年夜k乘積。
解題思緒：DP
設w(h,k) 表現: 從第1位到第K位所構成的十進制數,設m(i,j)表現前i位(1-i)分紅j段所得的最年夜乘積,則可獲得以下經典的DP方程：
if(j==1) m(i,j) = w(1,i) ;
if(j >=1 && j<=i) m(i,j) = max{m(d,j-1)*m(d+1,i)}
個中： 1<=d< i (即從1開端一向到i-1 中找最年夜值
else if(i < j) m(i,j) = 0 ;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 51
#define MAXK 10
long m[MAXK][MAXN]={{0,0}} ; /*初始化操作*/
long w[MAXN][MAXN]={{0,0}} ;
void maxdp(int n,int k,int *a)
{
int i,j,d,h,q,t,s;
long temp,max;
for(i=1; i<= n ; i++) /*分紅1段*/
m[i][1] = w[1][i];
for(i=1 ; i<= n ; i++) /* DP 進程*/
for(j=2; j<= k ; j++)
{
max = 0;
for(d=1; d < i ; d++)
if ( (temp = m[d][j-1]*w[d+1][i]) > max)
max = temp ;
m[i][j] = max ;
}
}
int main(void)
{
int n,k,i,j;
int a[MAXN]={0},la=0;
char c ;
scanf("%d %d ",&n,&k);
while ( ( c=getchar() )!=' ') /*讀入數據*/
{
a[++la] = c-'0' ;
}
for(i=1 ; i<= n; i++)
{
w[i][i]= a[i] ;
for(j=i+1 ; j<= n; j++)
w[i][j] = w[i][j-1]*10 + a[j] ;
}
/*
for(i=1 ; i<= n; i++)
{
for(j=1 ; j<= n; j++)
printf("%d ",w[i][j]);
printf(" ");
}
*/
maxdp(n,k,a) ;
printf("%ld ",m[n][k]) ;
/*system("pause");*/
return 0;
}
乘積最年夜成績：
（和最年夜k乘積成績差不多，都是用DP，不外有些細節要留意一下，好比：位數小於乘號，則為0)
描寫 Description
本年是國際數學同盟肯定的“2000——世界數學年”，又恰逢我國有名數學家華羅庚師長教師生日90周年。在華羅庚師長教師的故鄉江蘇金壇，組織了一場另具匠心的數學智力比賽的運動，你的一個好同伙XZ也有幸得以加入。運動中，掌管人給一切加入運動的選手出了如許一道標題：
設有一個長度N的數字串，請求選手應用K個乘號將它分紅K+1個部門，找出一種分法，使得這K+1個部門的乘積可以或許為最年夜。
同時，為了贊助選手可以或許准確懂得題意，掌管人還舉了以下的一個例子：
有一個數字串: 312，當N=3，K=1時會有以下兩種分法：
（1）3*12=36
（2）31*2=62
這時候，相符標題請求的成果是： 31*2=62
如今，請你贊助你的好同伙XZ設計一個法式，求得准確的謎底。
輸出格局 Input Format
法式的輸出共有兩行：
1.第一行共有2個天然數N，K (6<=N<=40，1<=K<=6)
2.第二行是一個K度為N的數字串。
輸入格局 Output Format
屏幕輸入(成果顯示在屏幕上)，絕對於輸出，應輸入所求得的最年夜乘積（一個天然數）。
解法： 典范的DP成績
設w(h,q)表現從h位開端的q位數字組合所成的十進制數,m(i,j)表現前i位數字串所得的最年夜j乘積,初始值為：
m(i,0) = w(1,q) ;
動規方程以下所示：
if (j==0) m(i,j) = w(1,q) ;
else if(j>0)
m(i,j) = max { m(d,j-1)*w(d+1,i-d) }
ps: 個中 1 <= d < i
代碼：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 51
#define MAXK 10
long m[MAXK][MAXN]={{0,0}} ; /*初始化操作*/
long my_10_pow(int t)
{
long sum=1 ;
int y;
for(y=1 ; y<= t ; y++)
sum *= 10 ;
return sum ;
}
long w(int start,int len,int *a)/*把數字串轉換成對應的十進制數*/
{
long res = 0 ;
int t,f;
for(f=start,t=len-1;t >= 0 ; f++,t--)
res += a[f]*my_10_pow(t) ;
return res ;
}
void maxdp(int n,int k,int *a)
{
int i,j,d,h,q,t,s;
long temp,max;
for(i=1; i<= n ; i++)
m[i][0] = w(1,i,a) ;
for(i=1 ; i<= n ; i++) /*DP 進程。。。。*/
for(j=1; j<= k ; j++)
{
max = 0;
if( i <= j) /*假如長度小於乘號的個數，則值為0*/
m[i][j] = 0 ;
else
{
for(d=1; d < i ; d++)
if ( (temp = m[d][j-1]*w(d+1,i-d,a)) > max)
max = temp ;
m[i][j] = max ;
}
}
}
int main(void)
{
int n,k,i,j;
int a[MAXN]={0},la=0;
char c ;
scanf("%d %d ",&n,&k);
while ( ( c=getchar() )!=' ') /*讀入數據*/
{
a[++la] = c-'0' ;
}
maxdp(n,k,a) ;
printf("max = %ld ",m[n][k]) ;
system("pause");
return 0;
}
