题解 - Vijos

0

llxfine LV 8 @ 2009-10-23 15:06:43

To oxilis: (^_^)

program p1378;

const

p=10000;

type

hp=array[0..20]of longint;

var

a:array[1..80,1..80]of longint;

tw:array[0..80]of hp;

f:array[1..80,1..80]of hp;

n,m,

i,j,k:longint;

sum:hp;

function multi(a:hp; x:longint):hp;

var

i:longint;

begin

fillchar(multi,sizeof(multi),0);

multi[0]:=a[0];

for i:=1 to multi[0] do multi[i]:=a[i]*x;

for i:=1 to multi[0] do

begin

multi:=multi+multi[i] div p;

multi[i]:=multi[i] mod p;

end;

if multi[multi[0]]>0 then inc(multi[0]);

while (multi[multi[0]]=0)and(multi[0]>1) do dec(multi[0]);

end;

function add(a,b:hp):hp;

var

i,l:longint;

begin

fillchar(add,sizeof(add),0);

if a[0]>b[0] then add[0]:=a[0] else add[0]:=b[0];

for i:=1 to add[0] do add[i]:=a[i]+b[i];

for i:=1 to add[0] do

begin

add:=add+add[i] div p;

add[i]:=add[i] mod p;

end;

if add[add[0]+1]>0 then inc(add[0]);

while (add[add[0]]=0)and(add[0]>1) do dec(add[0]);

end;

function max(a,b:hp):hp;

var

i:longint;

begin

if a[0]>b[0] then begin max:=a; exit; end

else if a[0]b[i] then

begin

max:=a; exit;

end

else if a[i]

0

student LV 8 @ 2009-10-22 11:00:02

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 338ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：519ms

一定要压位否则就会超时

0

赏金神侠PPF LV 7 @ 2009-10-21 21:34:24

高精度！

怎么不给数据的范围！

0

xiaoxiao-tg LV 7 @ 2009-10-13 23:49:16

本人第二个高精度和第一个DP高精度

共 408ms AC

高精度加法的形参值参

和DP得清零问题纠缠了我N久。。

积累经验吧 noip2009 ++

104 行

const maxn=100;

type arr=array[0..30] of integer;

var

a:array[1..maxn] of arr;

f:array[1..maxn,1..maxn] of arr;

sum:arr;

m,n:integer;

num:integer;

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

var i,num:integer;

begin

if a[0]>b[0] then exit(true);

if a[0]b[0]

then num:=a[0]

else

num:=b[0];

for i:=1 to num do

if a[i]+b[i]+j[i]>=10

then begin

c[i]:=(a[i]+b[i]+j[i]) mod 10;

inc(j);

end

else

c[i]:=a[i]+b[i]+j[i];

if j[num+1]0 then

begin

inc(num);

c[num]:=j[num];

end;

c[0]:=num;

end;

procedure work;

var i,j:integer;

now1,now2:arr;

begin

fillchar(now1,sizeof(now1),0);

fillchar(now2,sizeof(now2),0);

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

for i:=1 to m do

add(f,a[i],a[i]);

for i:=m downto 1 do

for j:=i+1 to m do

begin

add(now1,f,a[i]);

add(now2,f,a[j]);

if max(now1,now2) then

add(f,now1,now1)

else

add(f,now2,now2);

end;

end;

procedure print;

var i:integer;

begin

for i:=sum[0] downto 1 do

write(sum[i]);

writeln();

end;

procedure init;

var i,j,length:integer;

num:integer;{pay attention}

begin

readln(n,m);{n为行,m为列}

for i:=1 to n do

begin

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

for j:=1 to m do

begin

read(num);

change(num,j)

end;

readln();

work;

add(sum,sum,f[1,m]);

end;

end;

begin

init;

print;

end.

0

prince_hao LV 10 @ 2009-10-12 19:14:06

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 431ms

├ 测试数据 09：答案正确... 634ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1106ms

靠我程序垃圾

0

song19931218 LV 9 @ 2009-10-11 09:55:45

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：88ms

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

这是我的第一个高精度dp,程序写了100行,提交了3次。。。。。。。最后发现，前两次竟然是因为高精度加法处理不当的原因才挂的。。。。。郁闷

DP方程：

一种: F:=MAX（F+2^I*A[L]，F+2^I*A[R]）

另外一种：

F：=2*MAX（F+A[L]，F+A[R]）

我个人用的是第二种，因为编程复杂度较低。。。

然后降成２维+压四位高精度=AC

0

lishunzhi LV 9 @ 2009-10-08 13:39:34

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 40ms

├ 测试数据 08：答案正确... 430ms

├ 测试数据 09：答案正确... 649ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1119ms

var i,j,lengx,t,n,m,leng1,leng2,lengmax,k:longint;

f:array[-1..82,-1..82,0..100]of longint;

a,lengf:array[-3..100,-3..100]of longint;

leng,x1,x2,x,max1:array[0..100]of longint;

w:array[0..100,0..101]of longint;

function max(x,y:longint):longint;

begin

if x>y then max:=x else max:=y;

end;

procedure cheng(q:longint);

var i:longint;

begin

for i:=1 to leng[q-1] do w[q,i]:=w[q-1,i]*2;

for i:=1 to leng[q-1]-1 do

begin

inc(w[q,i+1],w[q,i] div 10);

w[q,i]:=w[q,i] mod 10;

end;

leng[q]:=leng[q-1];

while w[q,leng[q]]>=10 do

begin

inc(w[q,leng[q]+1],w[q,leng[q]] div 10);

w[q,leng[q]]:=w[q,leng[q]] mod 10;

inc(leng[q]);

end;

end;

procedure cheng1(x,y:longint);

var i,wei:longint;

begin

if a[t,x]=0 then leng1:=0

else

begin

wei:=x+m+1-y;

for i:=1 to leng[wei] do x1[i]:=w[wei,i]*a[t,x];

for i:=1 to leng[wei]-1 do

begin

inc(x1,x1[i] div 10);

x1[i]:=x1[i] mod 10;

end;

leng1:=leng[wei];

while x1[leng1]>=10 do

begin

inc(x1[leng1+1],x1[leng1] div 10);

x1[leng1]:=x1[leng1] mod 10;

inc(leng1);

end;

end;

end;

procedure cheng2(x,y:longint);

var i,wei:longint;

begin

if a[t,y]=0 then leng2:=0

else

begin

wei:=x+m+1-y;

for i:=1 to leng[wei] do x2[i]:=w[wei,i]*a[t,y];

for i:=1 to leng[wei]-1 do

begin

inc(x2,x2[i] div 10);

x2[i]:=x2[i] mod 10;

end;

leng2:=leng[wei];

while x2[leng2]>=10 do

begin

inc(x2[leng2+1],x2[leng2] div 10);

x2[leng2]:=x2[leng2] mod 10;

inc(leng2);

end;

end;

end;

procedure jia1(x,y:longint);

var max,i:longint;

begin

if lengf[x,y]>leng1 then max:=lengf[x,y] else max:=leng1;

for i:=1 to max do

begin

x1[i]:=x1[i]+f[x,y,i];

if x1[i]>=10 then

begin

inc(x1);

x1[i]:=x1[i]-10;

end;

end;

if x1[max+1]>0 then leng1:=max+1 else leng1:=max;

end;

procedure jia2(x,y:longint);

var max,i:longint;

begin

if lengf[x,y]>leng2 then max:=lengf[x,y] else max:=leng2;

for i:=1 to max do

begin

x2[i]:=x2[i]+f[x,y,i];

if x2[i]>=10 then

begin

inc(x2);

x2[i]:=x2[i]-10;

end;

end;

if x2[max+1]>0 then leng2:=max+1 else leng2:=max;

end;

function bijiao:longint;

var w:longint;

begin

if leng1>leng2 then bijiao:=1

else if leng10 do

begin

if x1[w]>x2[w] then

begin

bijiao:=1;

exit;

end;

if x1[w]lengmax then bijiao1:=1

else if lengf[x,x+1]0 do

begin

if max1[w]>f[x,x+1,w] then

begin

bijiao1:=2;

exit;

end;

if max1[w]lengx then max:=lengmax else max:=lengx;

for i:=1 to max do

begin

x[i]:=x[i]+max1[i];

if x[i]>=10 then

begin

inc(x);

x[i]:=x[i]-10;

end;

end;

if x[max+1]>0 then lengx:=max+1 else lengx:=max;

end;

begin

readln(n,m);

fillchar(x,sizeof(x),0);

w[0,1]:=1;

fillchar(leng,sizeof(leng),0);

leng[0]:=1;

for i:=1 to 82 do cheng(i);

for i:=1 to n do

for j:=1 to m do read(a);

lengx:=0;

for t:=1 to n do

begin

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

fillchar(lengf,sizeof(lengf),0);

for i:=0 to m do

for j:=m+1 downto i+1 do

begin

leng1:=0;

leng2:=0;

fillchar(x1,sizeof(x1),0);

fillchar(x2,sizeof(x2),0);

cheng1(i,j);

cheng2(i,j);

jia1(i-1,j);

jia2(i,j+1);

if bijiao=1 then

begin

f:=x1;

lengf:=leng1;

end;

if bijiao=2 then

begin

f:=x2;

lengf:=leng2;

end;

end;

fillchar(max1,sizeof(max1),0);

lengmax:=0;

for i:=0 to m do

if bijiao1(i)=1 then

begin

fillchar(max1,sizeof(max1),0);

for j:=1 to lengf do max1[j]:=f;

lengmax:=lengf;

end;

jia3;

end;

if lengx=0 then write(0);

for i:=lengx downto 1 do write(x[i]);

writeln;

end.

218行。写得太罗嗦了.勉勉强强过了

0

fp_yfw LV 10 @ 2009-10-06 17:36:31

orz lx and lxx

0

fp_wcw LV 9 @ 2009-10-06 17:26:17

Accepted 有效得分：100 有效耗时：9ms

题解

———————begin———————————————————

此题主要是

方程转移（很多大牛都因为想错或激动之类原因与省一over 掉了）

还有高精度问题（稍微不注意就 88 了）

和很多大牛不一样方程我是倒着推的

___|\__|\__|\__|\__| -_-\___|\__|\__|\__|\__|\__|\__|_

c[q] 为2的q次方预处理 b[]为读入的data

★ 每一行要分开处理{他们之间是没有关系的}

q=m时可预处理一下就 ok了 a:=b[i]*c[m];

q

0

hxlong LV 10 @ 2009-10-06 16:53:14

Accepted 有效得分：100 有效耗时：25ms

---|---|---|---|---|---|---|内有恶狗，切勿靠近---|---|---|---|---|---|---|---|---|---|---|---|---|时间还算可以吧

f(i,j)表示 I到J还没取，其他都取了

f(i,j)=max(f(i-1,j)+2^k*a,f(i,j+1)+2^k*a[j+1])

k=i+m-j-1

---|---|---|---|---|---|--内有宇智波，切勿靠近---|---|---|---|---|---|---|---|---|-

我的垃圾编译器，数组下标越界不提示，害我纠结半天

---|---|---|---|---|---|--内有one piece---|---|---|---|---|---|---|---|---|---|---|

for i:=1 to m do

for j:=m downto i do

begin

if(i=1)and(j=m)then continue;

k:=(i+m-(j+1));

dp:=max(dp+2^k*a,dp+2^k*a[j+1]);

end;

b:=0;

for i:=1 to m do

b:=max(b,dp+2^m*a[i]);

ans:=ans+b;

0

fp_gzc LV 10 @ 2009-10-06 16:15:09

Accepted 有效得分：100 有效耗时：284ms

---|---|~~~~~---|---|~~~性感的分割线~~~---|---|~~~~~~---|---|

时间还算看得过去

之前题解看不懂，看了sto大牛的方程，才得到启发.

ps：方程：

f=max{f+a[i]*2^(i+j),f+a[n-j+1]*2^(i+j)}　　

f表示每一行从左侧取i次，从右侧取j次的最大值

---|-**|*---|-**|*--华丽的分割线--**|*---|-**|*

自认为程序不是很长，贴出来分享一下（80行）

type

arr=array[0..100]of longint;

var

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

ans,ns,t:arr;

num:array[1..80,0..80]of arr;

s:array[0..80,0..80]of arr;

procedure add(var a,b:arr);

var jin,i,l:longint;

begin

if a[0]>b[0] then l:=a[0] else l:=b[0];

jin:=0;

for i:=1 to l do

begin

if i>a[0] then a[i]:=0;

if i=100000 then

begin

jin:=a[i] div 100000;

a[i]:=a[i] mod 100000;

end else jin:=0;

end;

if jin0 then begin inc(l); a[l]:=jin; end;

a[0]:=l;

end;

function bigger(var a,b:arr):boolean;

var i,j:longint;

begin

if a[0]>b[0] then exit(true) else

if b[0]>a[0] then exit(false) else

begin

for i:=a[0] downto 1 do

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

if a[i]=1 do

begin dec(n);

for i:=1 to m do

begin num:=1; read(num); end;

for i:=1 to m do

for j:=1 to m do

begin

num:=num;

add(num,num);

end;

for j:=0 to m do

for i:=0 to m-j do

begin

s:=0;

if i>0 then

begin

t:=num;

add(t,s);

if bigger(t,s) then s:=t;

end;

if j>0 then

begin

t:=num[m+1-j,i+j];

add(t,s);

if bigger(t,s) then s:=t;

end;

end;

ns[0]:=0;

for i:=0 to m do

if bigger(s,ns) then ns:=s;

add(ans,ns);

end;

write(ans[ans[0]]);

for i:=ans[0]-1 downto 1 do

begin

if ans[i]

0

rakerichard LV 8 @ 2009-09-12 20:17:35

一开始高精度的时候用的值传递调用，8、9数据超时

改了地址传递之后，全部数据9ms

0

Amita LV 8 @ 2009-08-16 14:13:15

都是0的时候，要注意下输出

0

myc427 LV 10 @ 2009-08-14 11:35:16

。残忍地用int64圧10位。。。还是不能秒杀。。应该尝试更高。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：113ms

终于AC了人生第一道高精度乘法。。。

0

飓风音速 LV 10 @ 2009-07-28 19:45:37

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：362ms

比较慢。开始数组开大了了，它说我超时。后来改小一点就AC了。

0

zhfgogogo LV 10 @ 2009-07-23 21:27:43

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一个多小时我的天啊........

0

mike_nzk LV 10 @ 2009-07-12 17:23:42

高精开到30正正好好，多了就内存溢出了

0

zhanghanyuan LV 10 @ 2009-07-08 07:08:44

好痛苦的高度酒精,都快把我毒死了

0

飞过海 LV 10 @ 2009-07-02 22:47:50

高精度……脱水了！小心TLE

0

sdvsdv LV 10 @ 2009-06-04 20:56:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 275ms

├ 测试数据 09：答案正确... 384ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：659ms

有点慢,因为我写高精偷了懒.

我觉得这是NOIP最难的DP,但是却不难在DP状态方程,而在于高精度.

题解

89 条题解

矩阵取数游戏

信息

状态

开发

支持

题解

89 条题解

矩阵取数游戏

信息

状态

开发

支持

还没有账户？

登录