NOIP第三题N^4的DP复测会不会出问题？
[i=s] 本帖最后由 cxh 于 2008-12-2 12:16 PM 编辑 [/i]福建的省测是330，但我第三题用的是N^4的dp，这几天我一直担心会不会是福建的机器太好了，放到北京就挂了。请问各位有没有用这种dp的，用它复测时会不会出问题？
晕死，还是超了，最后320，奇怪的是福建其他人用N^50还是100，大概人品不好吧...... 范围是50的话 有点危险... 山东的，也是。
50^4=6250000
3000^2=9000000
3000的数据应n2没问题吧？ 我要告诉楼主一个好消息。。。
我是n^5的算法。。。
估计最大点是0.3~0.4s 晕。。能做到5次方可是需要实力的阿。。
4次肯定可以的。 我N^4 没加任何剪枝最慢的一个点是0.85
但全国复测的机器比我们这还要好些~
所以应该不会超的~ - - 写费用流的飘过。 不会 var
a:array[0..50,0..50]of longint;
f:array[0..50,0..50,0..50,0..50]of longint;
i,j,i2,j2,n,m:longint;
begin
assign(input,'message.in');
assign(output,'message.out');
reset(input);
rewrite(output);
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do
read(a[i,j]);
readln;
end;
for i:=1 to m do
for j:=1 to n do
for i2:=1 to m do
for j2:=1 to n do
if ((i<>i2)and(j<>j2))or((i=m)and(i2=m)and(j=n)and(j2=n))
then begin
if i<>i2-1
then if f[i,j-1,i2-1,j2]+a[i,j-1]+a[i2-1,j2]>f[i,j,i2,j2]
then f[i,j,i2,j2]:=f[i,j-1,i2-1,j2]+a[i,j-1]+a[i2-1,j2];
if i-1<>i2-1
then if f[i-1,j,i2-1,j2]+a[i-1,j]+a[i2-1,j2]>f[i,j,i2,j2]
then f[i,j,i2,j2]:=f[i-1,j,i2-1,j2]+a[i-1,j]+a[i2-1,j2];
if j<>j2-1
then if f[i-1,j,i2,j2-1]+a[i-1,j]+a[i2,j2-1]>f[i,j,i2,j2]
then f[i,j,i2,j2]:=f[i-1,j,i2,j2-1]+a[i-1,j]+a[i2,j2-1];
if j-1<>j2-1
then if f[i,j-1,i2,j2-1]+a[i,j-1]+a[i2,j2-1]>f[i,j,i2,j2]
then f[i,j,i2,j2]:=f[i,j-1,i2,j2-1]+a[i,j-1]+a[i2,j2-1];
end;
writeln(f[m,n,m,n]);
close(input);
close(output);
end.
暴力的n^4,没问题的 我的n^3logn的=。= 4次怎么可能超……
能量项链写成100^4方的都100
不要说这题n最大就50了 心里还是没底... [quote]我的n^3logn的=。=
[size=2][color=#999999]macaroniz 发表于 2008-11-19 21:20[/color] [url=http://www.oibh.org/bbs/redirect.php?goto=findpost&pid=321171&ptid=27210][img]http://www.oibh.org/bbs/images/common/back.gif[/img][/url][/size][/quote]
偶O(N^3)的~~~还米优化~~~=。= 递推写了个(m+n)*n*n/2,然后加了范围剪枝。
预计在0.1s.
N^4预计在0.6s
一般来说，10^7是可以承受的。
50^4=6.25*10^6,可以说是完全没有问题。 关键是四重循环内部还有四个方向递推式的复杂度，难以保证暴力n^4里面的递推就是O（1）的时间.... var
f,s:array[0..50,0..50,0..50]of longint;
a:array[0..50,0..50]of longint;
i,j,k,m,n,l,p,ans:longint;
begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);
for k:=1 to n do
for i:=1 to m do
for j:=i to m do
s[k,i,j]:=s[k,i,j-1]+a[j,k];
for k:=1 to n do
for i:=1 to m do
for j:=i+1 to m do
for l:=1 to i do
for p:=i+1 to j do
if f[k,i,j]<f[k-1,l,p]+s[k,l,i]+s[k,p,j] then
f[k,i,j]:=f[k-1,l,p]+s[k,l,i]+s[k,p,j];
writeln(f[n,m-1,m]);
end. 同样的O(n[sup]4[/sup])，其实记忆化搜索更好实现。而且据我的程序看，还快一点。 送到北京的超时都被改成不超时的了 估计我什么机器都超不了...
看错题了 骗分写了个n^2的贪心..... ls很强大
页:
[1]
2