恶心的高精度。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

struct big{
int d[200],l;
void set(int x){for(int i=1;i<=l;i++)d[i]=0;d[1]=x;l=1;}
int operatorconst{return d[t];}
void operator+=(const big&o)
{
int v=0;l=max(l,o.l);
for(int i=1;i<=l;i++)
{
v+=d[i]+o[i];
d[i]=v%10;
v/=10;
}

if(v)d[++l]=v;
}
void operator *=(int x)
{
int v=0;
for(int i=1;i<=l;i++)
{
v+=d[i]*x;
d[i]=v%10;
v/=10;
}
while(v){
d[++l]=v%10;
v/=10;
}
}
void print(){for(int i=l;i>0;i--)printf("%d",d[i]);printf("\n");}
};

big max(big x,big y)
{
if(x.l>y.l)return x;
if(x.l<y.l)return y;
for(int i=x.l;i>=0;i--){
if(x.d[i]<y.d[i])return y;
if(x.d[i]>y.d[i])return x;
}
return x;
}

int i,j,l,p,n,m,s,t;
int a[100][100];
big k[100],f[100][100],temp,ans,num,fl,fr;

int main(){
scanf("%d%d\n",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)scanf("%d",&a[j][i]);
scanf("\n");
}
k[0].set(1);
for(i=1;i<=m+1;i++){k[i]=k[i-1];k[i]*=2;}
for(p=1;p<=n;p++)
{
for(l=1;l<=m-1;l++)
for(i=1;i<=l+1;i++)
{
s=i;t=m-(l-s+1);
fl=f[s-1][l-1];temp=k[l];temp*=a[s-1][p];fl+=temp;
fr=f[s][l-1];temp=k[l];temp*=a[t+1][p];fr+=temp;
f[s][l]=max(fl,fr);

}
ans.set(0);
for(i=1;i<=m;i++)
{
temp=k[m];temp*=a[i][p];
temp+=f[i][m-1];
ans=max(ans,temp);
}

num+=ans;

}
num.print();
return 0;
}

测试数据 #0: Accepted, time = 62 ms, mem = 3132 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 3132 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 3132 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 3132 KiB, score = 10
测试数据 #4: Accepted, time = 109 ms, mem = 3132 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 3132 KiB, score = 10
测试数据 #6: Accepted, time = 140 ms, mem = 3132 KiB, score = 10
测试数据 #7: Accepted, time = 374 ms, mem = 3132 KiB, score = 10
测试数据 #8: Accepted, time = 530 ms, mem = 3132 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 3128 KiB, score = 10
Summary: Accepted, time = 1478 ms, mem = 3132 KiB, score = 100

dp 但是要写高精度

编译通过... 

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

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

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

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

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

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

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

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

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

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

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

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

动归方程写麻烦了，泪流满面

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

通过这题。。把原先动辄300行的高精程序成功压缩到150行以内。

虽然时间慢了，但还是内牛满面。。^.^

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

倒霉，没秒杀

111 AC ~~纪念下~~

~~于11.11 21:11~~

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时|无输出...

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

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

Unaccepted 有效得分：90 有效耗时：56ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

没压位的高精 vijos的评测机还是不错的 本机上用cena测 8 9点都是0.7s和0.8s

比较悬。。。

万恶的高精...

type

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

var

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

sum:arr;

f:array[0..81,0..81] of arr;

a:array[0..81]of arr;

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

var

i:longint;

begin

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

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

if a[0]=b[0] then

begin

for i:=a[0] downto 1 do

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

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

end;

exit(a);

end;

procedure jia(var c:arr; a,b:arr);

var

i,j,x,len:longint;

begin

fillchar(c,sizeof(c),0);

x:=0;

if a[0]0 then

begin

inc(c[0]);

c[c[0]]:=x mod 10;

x:=x div 10;

end;

end;

procedure main;

var

i,j,k:longint;

r1,r2,r3:arr;

procedure print;

var

i,j:longint;

begin

for i:=f[1,m][0] downto 1 do write(f[1,m][i]); write(' ');

for i:=sum[0] downto 1 do write(sum[i]); writeln;

end;

begin

for i:=1 to m-1 do

for j:=1 to m-1 do

if i+j0 do

begin

inc(l);

x:=x div 10;

end;

a[y][0]:=l;

for i:=1 to a[y][0] do

begin

a[y][i]:=k mod 10;

k:=k div 10;

end;

end;

begin

readln(n,m);

fillchar(sum,sizeof(sum),0);

for i:=1 to n do

begin

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

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

for j:=1 to m do

begin

read(t);

zhuan(t,j);

jia(f[j,j],a[j],a[j]);

end;

main;

end;

for i:=sum[0] downto 1 do write(sum[i]);

end.

为什么我这么RP呢？只压四位就好~ ~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

www.hi.baidu.com\shuai_cannot

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

~~~~`~~~~~~`~~~~~~kid~~~~~`~~~~~~`~~~~~~

预处理(i=1 to m)f=a[k,i]

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

(f表示从i到j可以取的最大值)

只加法高精度且没有压位

~~~~~`~~~~~~`~~~~~~`~~~~~~kid~~~~~`~~~~~~`~~~~~~`~~~~~

type shuzu=array[0..100] of integer;

var jj,k,n,m,i,j,p,t,l:longint;

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

f,f1:array[0..80,0..80] of shuzu;

b:array[0..80] of shuzu;

t1,t2,sum:shuzu;

function kid(c,x,y:longint):shuzu;

var i,l:longint;

begin

for i:=0 to 100 do kid[i]:=0;

if f[x,y,0]>f[c,c,0] then l:=f[x,y,0]

else l:=f[c,c,0];

for i:=1 to l do

begin

kid[i]:=kid[i]+f[x,y,i]*2+f[c,c,i];

kid:=kid+kid[i] div 10;

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

end;

if kid[l+1]>0 then kid[0]:=l+1

else kid[0]:=l;

end;

begin

readln(n,m);

for i:=1 to n do

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

for k:=1 to n do

begin

f:=f1;

for i:=1 to m do

begin

j:=0;t:=a[k,i]*2;

while t>0 do

begin

inc(j);

f:=t mod 10;

t:=t div 10;

end;

f:=j;

end;

for i:=m downto 1 do

for j:=i+1 to m do

begin

t1:=kid(i,i+1,j);

t2:=kid(j,i,j-1);

if t1[0]>t2[0] then f:=t1

else

if t1[0]0) do dec(jj);

if t1[jj]>t2[jj] then f:=t1

else f:=t2;

end;

if f>b[k,0] then b[k]:=f

else if f=b[k,0] then

begin

jj:=b[k,0];

while (f=b[k,jj]) and (jj>0) do dec(jj);

if f>b[k,jj] then b[k]:=f;

end;

end;

if b[k,0]>sum[0] then l:=b[k,0]

else l:=sum[0];

for p:=1 to l do

begin

sum[p]:=sum[p]+b[k,p];

sum[p+1]:=sum[p+1]+sum[p] div 10;

sum[p]:=sum[p] mod 10;

end;

if sum[l+1]>0 then sum[0]:=l+1

else sum[0]:=l;

end;

if sum[0]=0 then writeln('0')

else

begin

for i:=sum[0] downto 1 do write(sum[i]);

writeln;

end;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

type arr=record

x:longint;

z:array[0..30] of longint;

end;

var a,b:array[-1..81,-1..81] of arr;

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

s1:string;

jm,max,m1,m2:arr;

function maxt(xt,yt:arr):arr;

var flg:boolean;

i:longint;

begin

fillchar(maxt,sizeof(maxt),0);

maxt:=xt;

if xt.x>yt.x then

maxt:=xt;

if xt.xyt.z[i] then

begin

maxt:=xt;

break;

end;

if yt.z[i]>xt.z[i] then

begin

maxt:=yt;

break;

end;

end;

end;

end;

function add(h1,h2:arr):arr;

var js,i:longint;

begin

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

if h1.x>h2.x then

js:=h1.x else

js:=h2.x;

for i:=1 to js do

add.z[i]:=h1.z[i]+h2.z[i];

add.x:=js;

for i:=1 to js-1 do

if add.z[i]>99999999 then

begin

inc(add.z,add.z[i] div 100000000);

add.z[i]:=add.z[i] mod 100000000;

end;

if add.z[js]>99999999 then

begin

inc(js);

add.z[js]:=add.z[js-1] div 100000000;

add.z[js-1]:=add.z[js-1] mod 100000000;

end;

add.x:=js;

end;

begin

fillchar(jm,sizeof(jm),0);

readln(n,m);

for i:=1 to n do

begin

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

fillchar(b,sizeof(b),0);

for j:=1 to m do

begin

read(b[0,j].z[1]);

b[0,j].x:=1;

end;

for j:=1 to m do

for k:=1 to m do

b[k,j]:=add(b[k-1,j],b[k-1,j]);

for j:=1 to m do

for k:=0 to j do

begin

m1:=add(a[j-1,k-1],b[j,k]);

m2:=add(a[j-1,k],b[j,m-j+k+1]);

a[j,k]:=maxt(m1,m2);

end;

fillchar(max,sizeof(max),0);

for j:=1 to m do

max:=maxt(a[m,j],max);

jm:=add(jm,max);

end;

write(jm.z[jm.x]);

for i:=jm.x-1 downto 1 do

begin

str(jm.z[i],s1);

for j:=1 to 8-length(s1) do

write(0);

write(s1);

end;

writeln;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

type arr=record

x:longint;

z:array[0..30] of longint;

end;

var a,b:array[0..81,0..81] of arr;

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

s1:string;

jm,max,m1,m2,fs:arr;

function maxt(xt,yt:arr):arr;

var flg:boolean;

i:longint;

begin

fillchar(maxt,sizeof(maxt),0);

if xt.x>yt.x then

maxt:=xt;

if xt.xyt.z[i] then

begin

maxt:=xt;

break;

end;

if xt.z[i]h2.x then

begin

js:=h1.x;

//for i:=h2.x+1 to js do

// h2.z[i]:=0;

end

else

begin

js:=h2.x;

//for i:=h1.x+1 to js do

//h1.z[i]:=0;

end;

for i:=1 to js do

add.z[i]:=h1.z[i]+h2.z[i];

add.x:=js;

for i:=1 to js-1 do

if add.z[i]>99999999 then

begin

inc(add.z,add.z[i] div 100000000);

add.z[i]:=add.z[i] mod 100000000;

end;

while add.z[js]>99999999 do

begin

inc(js);

add.z[js]:=add.z[js-1] div 100000000;

add.z[js-1]:=add.z[js-1] mod 100000000;

end;

add.x:=js;

end;

begin

fillchar(jm,sizeof(jm),0);

readln(n,m);

for i:=1 to n do

begin

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

fillchar(b,sizeof(b),0);

for j:=1 to m do

begin

read(b[0,j].z[1]);

if b[0,j].z[1]0 then

b[0,j].x:=1;

b[0,j]:=add(b[0,j],fs);

end;

for j:=1 to m do

for k:=1 to m do

b[k,j]:=add(b[k-1,j],b[k-1,j]);

for j:=1 to m do

a[j,j]:=b[m,j];

for k:=1 to m-1 do

for j:=1 to m-k do

begin

l:=j+k;

{if k=m then a[j,l]:=add(a[j-1,k-1],b[j,k]);

if k=0 then a[j,l]:=add(a[j-1,k],b[j,m-j+k+1]);

if (k0)and(km) then }

{m1:=add(add(a[j,l-1],a[j,l-1]),b[1,l]);

m2:=add(add(a[j+1,l],a[j+1,l]),b[1,j]);

a[j,l]:=maxt(m1,m2);}

a[j,l]:=maxt(add(a[j+1,l],b[m-k,j]),add(a[j,l-1],b[m-k,l]));

{ a[j,l]:=maxt(a[j,l],);}

end;

{fillchar(max,sizeof(max),0);

for j:=0 to m do

max:=maxt(a[m,j],max);

jm:=add(jm,max); }

jm:=add(jm,a[1,m]);

end;

for i:=1 to jm.x-1 do

if jm.z[i]>99999999 then

begin

jm.z:=jm.z+jm.z[i] div 100000000;

jm.z[i]:=jm.z[i] mod 100000000;

end;

while jm.z[jm.x]>99999999 do

begin

inc(jm.x);

jm.z[jm.x]:=jm.z[jm.x-1] div 100000000;

jm.z[jm.x-1]:=jm.z[jm.x-1] mod 100000000;

end;

write(jm.z[jm.x]);

for i:=jm.x-1 downto 1 do

begin

str(jm.z[i],s1);

for j:=1 to 8-length(s1) do

write(0);

write(s1);

end;

// write(jm.z[i]);

writeln;

end.

第一次90分...输出子程序里忘了给初值了

第2次AC了... 整个程序都成了高精度

100题纪念

终于AC了。。前前后后断断续续从暑假开始做的。。

昨天发现DP方程有问题。。

高精都写了N遍了。。

抽。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

交了4次...压4位到9 预处理....

const q=10000;

type arr=array[0..10] of longint;

var f:array[1..80,1..80] of arr;

a:array[0..80] of longint;

b:array[0..80] of arr;

q1,c:arr;

n,m:longint;

procedure jia(a,b:arr; var c:arr);

var i,l:longint;

begin

fillchar(c,sizeof(c),0);

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

for i:=1 to l do c[i]:=a[i]+b[i];

for i:=1 to l do

if c[i]>=q then

begin c[i]:=c[i]-q; inc(c); end;

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

c[0]:=l;

end;

procedure cheng(a,b:arr; var c:arr);

var i,j,l:longint;

begin

fillchar(c,sizeof(c),0);

for i:=1 to a[0] do

for j:=1 to b[0] do

begin

l:=i+j-1;

inc(c[l],a[i]*b[j]);

inc(c[l+1],c[l] div q);

c[l]:=c[l] mod q;

end;

l:=a[0]+b[0]; while (c[l]=0) and (l>0) do dec(l);

c[0]:=l;

end;

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

var i:longint;

begin

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

for i:=a[0] downto 1 do

begin

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

end;

exit(false);

end;

procedure work;

var i,h,j:longint;

t1,t2,t3,t4:arr;

begin

for i:=1 to m do

begin

read(a[i]); c[0]:=1; c[1]:=a[i];

cheng(c,b[m],f);

end;

for h:=1 to m-1 do

for i:=1 to m-h do

begin

j:=i+h;

c[0]:=1; c[1]:=a[i]; cheng(c,b[m-h],t1);

jia(f,t1,t2);

c[0]:=1; c[1]:=a[j]; cheng(c,b[m-h],t3);

jia(f,t3,t4);

if da(t2,t4) then f:=t2 else f:=t4;

end;

jia(q1,f[1,m],q1);

end;

procedure put(x:longint);

var l,i:integer;

begin

l:=trunc(ln(x)/ln(10))+1;

for i:=1 to 4-l do write('0'); write(x);

end;

procedure ready;

var i:longint;

begin

readln(n,m);

c[0]:=1; c[1]:=2;

b[0,0]:=1; b[0,1]:=1;

for i:=1 to m do cheng(b,c,b[i]);

for i:=1 to n do work;

write(q1[q1[0]]);

for i:=q1[0]-1 downto 1 do put(q1[i]); writeln;

end;

begin

ready;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

同样的代码打两遍.....可怜的ac率啊....

高精度啊！！

让我多调了半个小时……

我无语。。

这道题充分证明了本人有多菜。。

Ac的路幽邃而漫长。大致可分5步走。。

1.首先这道题是动归，毋庸置疑，心中一喜，迅速做完，一测，0分。。原来是太过激动，循环和边界没考虑清楚。。

2.改好开longint,40分。。int64，60分。。再一次郁闷。

3.我一开始用的是 F:=MAX（F+2^I*A[i]，F+2^I*A[j]） 这个方程，写高精乘高精，改到吐血也没改对，总有些莫名其妙的问题。最后秉承一个宗旨：如果程序无论如何也改不对，最好的方法就是重新写一遍。

4.在重写的过程中借鉴了大牛们的巧妙方法，用了如下方程：

f:=max(f+a[i],f+a[j])*2;

预处理： for i:=1 to m do

f:=2*a[i];

大大降低了编程复杂度。最后提交，没压位，80分。。

5.在压了100000进制后，终于ac。