讨论 / 求解= =
SunFrank 2011-10-29 05:33:00
点我顶贴 收藏 删除
const

mm=10000;

h=20;

type

arr=array[1..h]of longint;

var

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

a:array[1..4]of longint;

f:array[-100000..100000]of arr;

a1,a2:arr;

function t1(a,b:arr):arr;

var i:longint;tmp:arr;

begin

fillchar(tmp,sizeof(tmp),0);

for i:=1 to h-1 do

begin

tmp[i]:=tmp[i]+a[i]+b[i];

tmp[i+1]:=tmp[i]div mm;

tmp[i]:=tmp[i]mod mm;

end;

exit(tmp);

end;

function t2(a:arr):arr;

var i:longint;tmp:arr;

begin

fillchar(tmp,sizeof(tmp),0);

for i:=1 to h-1 do

begin

tmp[i]:=tmp[i]+a[i]*2;

tmp[i+1]:=tmp[i]div mm;

tmp[i]:=tmp[i]mod mm;

end;

exit(tmp);

end;

function comp(a,b:arr):boolean;

var i:longint;

begin

for i:=h downto 1 do

if a[i]>b[i]then exit(true)

else if a[i]<b[i]then exit(false);

exit(true);

end;

begin

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

assign(output,'1.out');rewrite(output);

read(n);

for i:=1 to 4 do

read(a[i]);

a[2]:=a[2]+a[3]+a[4]+a[4];

a[3]:=a[4];

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

f[a[1]][1]:=1;

for i:=a[1]+1 to n do

begin

f[i]:=f[i-a[1]];

inc(f[i][1]);

a2:=t1(f[i-a[3]],a1);

if comp(a2,f[i])then f[i]:=a2;

a2:=t2(f[i-a[2]]);

if comp(a2,f[i])then begin f[i]:=a2;a1:=f[i-a[2]];end;

end;

j:=h; while f[n][j]=0 do dec(j);

write(f[n][j]);

dec(j);

for i:=j downto 1 do

begin

if f[n][i]<1000 then write(0);

if f[n][i]<100 then write(0);

if f[n][i]<10 then write(0);

write(f[n][i]);

end;

writeln;

close(output);

end.

状态: Unaccepted

测评机: Xeost[5]

得分: 30分

提交日期: 2011-10-24 7:38:00

有效耗时: 579毫秒

测试结果1: 通过本测试点|有效耗时204ms

测试结果2: 通过本测试点|有效耗时187ms

测试结果3: 通过本测试点|有效耗时188ms

测试结果4: 测试结果错误.

 错误结果为:941281712193427043205975800631852798750517886976

正确结果应为:6938893903907228377647697925567626953125000000

测试结果5: 测试结果错误.

 错误结果为:8227522786606030210774845912786752524913679328167899316743045120

正确结果应为:135089572145988893225762952830814975460584044389210917814356934656

测试结果6: 测试结果错误.

 错误结果为:695256752686334109739257841379109240832

正确结果应为:2907686240779503471977077944363253760

测试结果7: 测试结果错误.

 错误结果为:204786097568403779690635866791836

正确结果应为:6338253001141147007483516026880

测试结果8: 测试结果错误.

 错误结果为:47160738310954332686083491445650074662712846369103364436387844

正确结果应为:1204652787946159667410483115524630264881874960266110061462801408

测试结果9: 测试结果错误.

 错误结果为:427962040806026614161442508409591188

正确结果应为:9507379501711720511225274040320000

测试结果10: 测试结果错误.

 错误结果为:396172442448217495331157329849569615189901312

正确结果应为:5329070518200751394033432006835937500000000

#1 LostInForever@2011-10-29 04:43:00
回复 删除
高精度吧。。。
#2 LostInForever@2011-10-29 05:33:00
回复 删除
貌似要用O(n^2)的动态规划才行吧……
查看更多回复
提交回复