90 条题解
-
0
laijingtao LV 8 @ 2009-10-23 18:44:09
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 56ms
├ 测试数据 07：答案正确... 181ms
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：237msFlag Accepted
题号 P1378
类型(?) 动态规划
通过 957人
提交 3932次
通过率 24%
难度 2无语......
-
0
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
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 181ms
├ 测试数据 09：答案正确... 338ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：519ms
一定要压位 否则就会超时 -
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
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 40ms
├ 测试数据 08：答案正确... 430ms
├ 测试数据 09：答案正确... 649ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1119msvar 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
Accepted 有效得分：100 有效耗时：9ms
题解
———————begin———————————————————
此题主要是方程转移（很多大牛都因为想错或激动之类原因与 省一over 掉了）
还有高精度问题 （稍微不注意 就 88 了）
和很多大牛不一样 方程我是倒着推的
___|\__|\__|\__|\__| -_-\___|\__|\__|\__|\__|\__|\__|_
c[q] 为2的q次方 预处理 b[]为读入的data
★ 每一行要分开处理{他们之间是没有关系的}
q=m时 可预处理一下就 ok了 a:=b[i]*c[m];
q -
0
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
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
。残忍地用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
编译通过...
├ 测试数据 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
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms一个多小时 我的天啊........
-
0
zhanghanyuan LV 10 @ 2009-07-08 07:08:44
好痛苦的高度酒精,都快把我毒死了
laijingtao
LV 8
@ 2009-10-23 18:44:09
信息
- ID
- 1378
- 难度
- 7
- 分类
- 动态规划 | 高精度 点击显示
- 标签
- 递交数
- 4646
- 已通过
- 1055
- 通过率
- 23%
- 被复制
- 9
- 上传者
-
wojiubuxing
