PASCAL乘積最大高精度動態規劃寫法求高手查錯

1樓：

const maxn=40;

maxk=6;

vari,j,l:longint;

n,k:longint;

s:string;

f:array[0..maxn,0..maxk] of int64;

a:array[0..maxn,0..maxn] of int64;

begin

readln(n,k);

readln(s);

fillchar(f,sizeof(f),0);

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

j:=ord(s[i]);

dec(j,ord('0'));

a[i,i]:=j;

end;

for i:=1 to n do

for j:=i+1 to n do a[i][j]:=a[i][j-1]*10+a[j][j];

for i:=1 to n do f[i][0]:=a[1][i];

for l:=1 to k do

for i:=l+1 to n do

begin

for j:=l-1+1 to i-1 doif f[i][l]

end;

writeln(f[n][k]);

end.

2樓：匿名使用者

這道題不用高精度的 int64就可以過了

var sum,f:array[0..50,0..20]of int64;

n,m,i,j,k:longint;

max:int64;

st:string;

begin

readln(n,m);

readln(st);

for i:=1 to n do val(copy(st,1,i),f[i,0]);

for i:=1 to n do

for j:=i to n do

val(copy(st,i,j-i+1),sum[i,j]);

for i:=1 to n do

for j:=1 to i-1 do

begin

max:=0;

for k:=1 to i do

if max

f[i,j]:=max;

end;

writeln(f[n,m]);

end.

pascal乘積最大問題

3樓：匿名使用者

我們一起來分析一下：

設字串長度為n，乘號數為k，如果n=50,k=1時，

有（n-1）=49種不同的乘法，當k=2時，有c(2，50-1)=1176種乘法，既c(k,n-1)種乘法，當n、k稍微大一些的時候，用窮舉的方法就不行了。

設數字字串為a1a2…an

k=1時：一個乘號可以插在a1a2…an中的n-1個位置，這樣就得到n-1個子串的乘積：

a1*a2…an, a1a2*a3…an, …, a1a2…a n-1*an (這相當於是窮舉的方法)

此時的最大值=max

k=2時，二個乘號可以插在a1a2…an中n-1個位置的任兩個地方， 把這些乘積

分個類，便於觀察規律：

①倒數第一個數作為被乘數：

a1*a2 …a n-3 a n-2 a n-1*an，

a1a2 …*a n-2 a n-1*an，

a1a2 …*a n-1*an。

設符號f[n-1,1]為在前n-1個數中插入一個乘號的最大值,則的最大值為

f[n-1,1]*an。

②倒數第二個數作為被乘數：

a1*a2 …an-3 a n-2* a n-1，

an … a1a2 …*a n-2*a n-1an，

a1a2…*a n-3 a n-2* a n-1 an。

設符號f[n-2,1]為在前n-2個數中插入一個乘號的最大值,則的最大值為

f[n-2,1]*a n-1 an

③倒數第三個數作為被乘數：

… 設符號f[n-3,1]為在前n-3個數中插入一個乘號的最大值,則的最大值為

f[n-3,1]*a n-2 a n-1 an

…… a3~an作為被乘數：f[2,1]*a3 …a n-2 a n-1 an

此時的最大乘積為：

f[n,k]=max

設f[i,j]表示在 i 個數中插入 j 個乘號的最大值，g[i,j]表示從ai到aj的數字列，則可得到動態轉移方程：

f[i,j] = max

(1<=i<=n, 1<=j<=k)

邊界： f[i,0] =g[1,i] （數列本身）

階段：子問題是在子串中插入j-1,j-2……1,0個乘號，因此乘號個數作為階段的劃分（j個階段）

狀態：每個階段隨著被乘數數列的變化劃分狀態。

決策：在每個階段的每種狀態中做出決策。

資料結構：

（此題不需要高精度，pascal用longint即可ac)

int n,k; /* n為數字個數，k為劃分個數*/

int i,j,l; /*迴圈變數*/

char c; /*字元讀入*/

int data[50]=; /*存數字的陣列*/

int g[50][50],f[50][10]; /*g為數字列，f為動態規劃陣列*/

初始化：

cin >> n >> k; /*讀入,n,k*/

for(i=1;i<=n;i++)

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

g[i][j]=g[i][j-1]*10+data[j]; /*初始化數列*/

for(i=1;i<=n;i++)

f[i][0]=g[1][i]; /*初始化動態規劃陣列*/

動態規劃：

for(i=1;i<=n;i++)/*方程：f[i,j]表示前i個數中插入j個*號的最優值。*/

for(j=1;j<=i+1;j++)

for(l=1;l<=i-1;l++)

f[i][j]=max(f[i][j],f[l][j-1]*g[l+1][i]);

輸出f[n][k]

4樓：匿名使用者

這是動規題

並且是noip上 吧

不難看看題解就知道了

c 高精度階乘，c 高精度階乘

include 萬能標頭檔案 using namespace std int a 100000 n,i,y,xy 100000 s 100000 s 0 和a 0 表示兩個陣列的長度 s表示答案，a表示階乘，先算出階乘，放在a裡，再把s和它相加，更新s void add 表示s s a while ...

高精度求組合數後10 位 15

高精度求組合數後10 位 n r分別代表什麼？你沒說清楚。0到9十個數字 的十位陣列合有多少种情況？最高位不能是0，所以最高位有9種組合。最高位佔了乙個數，其它位可以是0，所以第九位有9種組合前兩位佔了兩個數，所以第三位有8種組合。最後一位只剩下1個數，所以末尾只有1種組合所以共有9 9 8 7 6...

哪裡可以下到MAYA高精度或者次世代模型

想要系統的學習可以考慮報一個網路直播課，推薦cgwang的網路課。老師講得細，上完還可以回旦襲看，還有同型別錄播課可以免費學 贈送終身vip 在 maya影視製作 領域的培訓機構裡，王氏教育 是國內的老大，且沒有加盟分校，都是總部直營的連鎖校區。跟很多其它同型別大機構不一樣的是 王氏教育每個校區都是...