163 条题解
-
0
skq大牛 LV 8 @ 2009-08-14 11:29:18
我好弱……我写的高精……~~~~(>_
-
0
var i,j,k,m,n:longint;
s:string;
f:array[0..40,0..6] of longint;
{f 代表 前i个数 放了j个乘号 的最大值}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
function g(x,y:longint):longint;
begin
val(copy(s,x,y-x+1),g);
end;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
begin
readln(n,m);
readln(s);
for i:=1 to n do f:=g(1,i);
{f 放0个乘号当然是g(1,i)}for i:=1 to n do
{i枚举前n个数}
for j:=1 to i+1 do
{枚举放j个乘号}
for k:=1 to i-1 do
{枚举在第k个位置仿乘号}
f:=max(f,f[k,j-1]*g(k+1,i));writeln(f[n,m]);
end. -
0
zhanghanyuan LV 10 @ 2009-08-07 20:07:31
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
数据,我对你无语了 -
0
（给向我一样的菜鸟一些提示）
我们一起来分析一下：
设字符串长度为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{a1*a2…an, a1a2*a3…an, … , a1a2…a n-1*an }
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[n-1]*an，F[n-2,1]*a n-1 an，
F[n-3,1]*a n-2 a n-1 an，
F[2,1]*a3 …a n-2 a n-1 an}
设F表示在 i 个数中插入 j 个乘号的最大值，g表示从ai到aj的数字列，则可得到动态转移方程：
F = max{F*g, F*g,
F*g, …., F[j,j-1]*g[j+1,i]}
(1 k; /*读入,n,k*/
for(i=1;i> c; /*读入一个数字*/
data[i]=c-'0'; /*字符转化数字*/
g[i][i]=data[i];/*初始化数列*/
}
for(i=1;i-
大王叫我来巡山 @ 2016-10-12 19:41:48
谢谢
-
-
0
liuyuyaowww LV 9 @ 2009-07-31 17:07:54
program leo;
var n,m,i,j,k:longint;
s:string;
f:array[0..40,0..6]of longint;
function g(x,y:longint):longint;
begin
val(copy(s,x,y-x+1),g);
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
begin
readln(n,m);
readln(s);
for i:=1 to n do f:=g(1,i);
for i:=1 to n do
for j:=1 to i+1 do
for k:=1 to i-1 do
f:=max(f,f[k,j-1]*g(k+1,i));
writeln(f[n,m]);
end. -
0
NaTuReHugh LV 9 @ 2009-07-27 00:22:54
15分钟，秒杀~感动ING
Program P1347;
var s:string;
k,i,j,n,m,v:longint;
f:array[0..100,0..100] of longint;function change(i,j:longint):longint;
begin
val(copy(s,i,j-i+1),change);
end;function max(a,b:longint):longint;
begin
if a=j then
for k:=1 to i-1 do
f:=max(f,f[k,j-1]*change(k+1,i));writeln(f);
end. -
0
var
c:array[0..100,0..100] of extended;
n,i,j,k,l:integer;
max,t:extended;
s:string;function f(q,m:integer):extended;
begin
f:=0;
while m>0 do
begin
f:=f*10+ord(s[q])-48;
inc(q);dec(m);
end;
end;begin
readln(n,l);
readln(s);
for i:=1 to n do c[0,i]:=f(1,i);
for i:=1 to l do
for j:=1 to n do
begin
max:=0;
for k:=j-1 downto 1 do
begin
t:=f(k+1,j-k);
if c*t>max then max:=c*t;
end;
c:=max;
end;
writeln(c[l,n]:0:0);
end.
看大家的程序都好长哦
但是自己做就这么点短，真是郁闷~ -
0
yulingtai01 LV 9 @ 2009-07-20 21:17:12
动归中的经典题型最大k乘积？？
刚刚看过一个教程
.状态转移方程 f:=max(f[k,j-1]*num[k+1,i){k:=j to i-1);
秒了 -
0
zhangjian555 LV 8 @ 2009-07-17 18:06:29
program productmax;
type
xx=array[0..41]of longint;
var
s:ansistring;
n,k:longint;
f:array[0..41,0..41]of xx;
a:array[0..41,0..41]of xx;
procedure init;
var
i,j,h:longint;
begin
assign(input,'productmax.in');
assign(output,'productmax.out');
reset(input);
rewrite(output);
readln(n,k);
readln(s);
for i:=1 to n do
for j:=i to n do
begin
a[0]:=j-i+1;
for h:=1 to a[0] do
a[h]:=ord(s[j-h+1])-48;
end;
for i:=1 to n do f:=a[1,i];
end;
function cheng(a,b:xx):xx;
var
c:xx;
i,j:longint;
begin
fillchar(c,sizeof(c),0);
c[0]:=a[0]+b[0];
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
c:=a[i]*b[j]+c;
c:=c+c div 10;
c:=c mod 10;
end;
while (c[c[0]]=0)and(c[0]>1) do dec(c[0]);
cheng:=c;
end;
function max(a,b:xx):boolean;
var
i,j:longint;
begin
if a[0]>b[0] then begin max:=true; exit; end;
if a[0]b[i] then begin max:=true; exit; end;
if a[i] -
0
program pp1347;
type
num=array[0..50]of longint;
var
s:String;
n,k:longint;
f,a:array[0..50,0..50,0..50]of longint;
procedure init;
var
i,j,m:longint;
begin
assign(input,'productmax.in');
reset(input);
assign(output,'productmax.out');
rewrite(output);
readln(n,k);
readln(s);
for i:=1 to n do
for j:=i to n do
begin
a:=j-i+1;
for m:=1 to a do
a:=ord(s[j-m+1])-48;
end;
for i:=1 to n do
f:=a[1,i];
end;
function cheng(x,y:num):num;
var
i,j:longint;
xx:num;
begin
fillchar(xx,sizeof(xx),0);
for i:=1 to x[0] do
for j:=1 to y[0] do
begin
xx[j+i-1]:=xx[j+i-1]+x[i]*y[j];
xx[j+i]:=xx[j+i]+xx[j+i-1]div 10;
xx[j+i-1]:=xx[j+i-1]mod 10;
end;
xx[0]:=x[0]+y[0];
while (xx[0]>1)and(xx[xx[0]]=0) do dec(xx[0]);
cheng:=xx;
end;
function compare(x,y:num):boolean;
var
i:longint;
begin
if x[0]>y[0] then exit(false);
if x[0]y[i] then exit(false);
if x[i] -
0
one...two...three...four...five....six
............
一遍AC...program hlg;
var
i,k,n,temp,code:longint;
maxnum:int64;
st:string[40];
ch:char;procedure one;
var
a:integer;
n1,n2:longint;
begin
for a:=2 to n do
begin
val(copy(st,1,a-1),n1,code);
val(copy(st,a,n-a+1),n2,code);
if n1*n2>maxnum then maxnum:=n1*n2;
end;
end;procedure two;
var
a,b:integer;
n1,n2,n3:longint;
begin
for a:=2 to n do
for b:=a+1 to n do
begin
val(copy(st,1,a-1),n1,code);
val(copy(st,a,b-a),n2,code);
val(copy(st,b,n-b+1),n3,code);
if n1*n2*n3>maxnum then maxnum:=n1*n2*n3;
end;
end;procedure three;
var
a,b,c:integer;
n1,n2,n3,n4:longint;
begin
for a:=2 to n do
for b:=a+1 to n do
for c:=b+1 to n do
begin
val(copy(st,1,a-1),n1,code);
val(copy(st,a,b-a),n2,code);
val(copy(st,b,c-b),n3,code);
val(copy(st,c,n-c+1),n4,code);
if n1*n2*n3*n4>maxnum then maxnum:=n1*n2*n3*n4;
end;
end;procedure four;
var
a,b,c,d:integer;
n1,n2,n3,n4,n5:longint;
begin
for a:=2 to n do
for b:=a+1 to n do
for c:=b+1 to n do
for d:=c+1 to n do
begin
val(copy(st,1,a-1),n1,code);
val(copy(st,a,b-a),n2,code);
val(copy(st,b,c-b),n3,code);
val(copy(st,c,d-c),n4,code);
val(copy(st,d,n-d+1),n5,code);
if n1*n2*n3*n4*n5>maxnum then maxnum:=n1*n2*n3*n4*n5;
end;
end;procedure five;
var
a,b,c,d,e:integer;
n1,n2,n3,n4,n5,n6:longint;
begin
for a:=2 to n do
for b:=a+1 to n do
for c:=b+1 to n do
for d:=c+1 to n do
for e:=d+1 to n do
begin
val(copy(st,1,a-1),n1,code);
val(copy(st,a,b-a),n2,code);
val(copy(st,b,c-b),n3,code);
val(copy(st,c,d-c),n4,code);
val(copy(st,d,e-d),n5,code);
val(copy(st,e,n-e+1),n6,code);
if n1*n2*n3*n4*n5*n6>maxnum then maxnum:=n1*n2*n3*n4*n5*n6;
end;
end;procedure six;
var
a,b,c,d,e,f:integer;
n1,n2,n3,n4,n5,n6,n7:longint;
begin
for a:=2 to n do
for b:=a+1 to n do
for c:=b+1 to n do
for d:=c+1 to n do
for e:=d+1 to n do
for f:=e+1 to n do
begin
val(copy(st,1,a-1),n1,code);
val(copy(st,a,b-a),n2,code);
val(copy(st,b,c-b),n3,code);
val(copy(st,c,d-c),n4,code);
val(copy(st,d,e-d),n5,code);
val(copy(st,e,f-e),n6,code);
val(copy(st,f,n-f+1),n7,code);
if n1*n2*n3*n4*n5*n6*n7>maxnum then maxnum:=n1*n2*n3*n4*n5*n6*n7;
end;
end;begin {main}
maxnum:=0;
st:='';
readln(n,k);
for i:=1 to n do
begin
read(ch);
st:=st+ch;
end;
case k of
1:one;
2:two;
3:three;
4:four;
5:five;
6:six;
end;
writeln(maxnum);
end.
skq大牛
LV 8
@ 2009-08-14 11:29:18
