讨论 / 测试数据5组对3组,问题在哪啊?
冰雪ぃ梓星 2011-10-03 19:23:00
点我顶贴 收藏 删除
program fgqs;

var

a:array [0..10,0..10] of integer;

f:array [0..10,0..10] of integer;

i,j,n,sum:integer;

procedure qs;{动规求f[1,1]到f[n,n]最大值}

begin

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

for i:=1 to n do

for j:=1 to n do

if f[i-1,j]>f[i,j-1]

then f[i,j]:=f[i-1,j]+a[i,j]

else f[i,j]:=f[i,j-1]+a[i,j];;;

sum:=sum+f[n,n];

end;

procedure fh;{返回查找取过的数a[i,j]赋值为0}

begin

i:=n;

j:=n;

repeat

if f[i,j]=f[i-1,j]+a[i,j]

then begin

a[i,j]:=0;

i:=i-1;

end

else begin

a[i,j]:=0;

j:=j-1;

end;

until i=0;

end;

begin

readln(n);

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

repeat

readln(i,j,a[i,j]);

until (i=0) and (j=0) and (a[i,j]=0);

sum:=0;{以上为初始化}

qs;

fh;

qs;

write(sum);

end.

#1 冰雪ぃ梓星@2008-08-17 07:24:00
回复 删除
打错了,是5组对4组。

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

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

测试结果3: 测试结果错误.错误结果为:23

正确结果应为:25

测试结果4: 通过本测试点|有效耗时47:ms

测试结果5: 通过本测试点|有效耗时47:ms

#2 vinence@2008-08-17 07:41:00
回复 删除
这证明你有一些细节没考虑到,

或者是数据问题.

#3 冰雪ぃ梓星@2008-08-17 18:42:00
回复 删除
能不能发一下提示结果错误的第3组测试数据?

顺便建议一下,能不能把测试数据在测试结果中显示?

#4 cth@2008-08-18 21:02:00
回复 删除
你的思路好象就是错误的。

如果先dp一次,处理取过的数后再dp第二次。这样做.......不知道怎么说,反正感觉带有贪心的观念,带来了后效性。

我的做法是同时计算两条路的最大值,就是所谓的多进程dp吧。按对角线划分阶段,共计2n-1个阶段。

f[i][x][y]第i个阶段,两条路分别走到x和y点的最大值

枚举x点的上两个点的,y点的上两个点,共分析上一阶段的4个f()值,取其最大。

如果x=y,只加一次该点的值。

如果x<>y,分别加上x和y所在点的数值。

最后输出最后阶段的f值,100ms搞定Ac

#5 冰雪ぃ梓星@2008-08-18 21:25:00
回复 删除
非常感谢!!!!!!!
#6 wxfred@2008-08-20 06:21:00
回复 删除
三楼说的没错
#7 飞雪天涯@2008-10-19 08:20:00
回复 删除
#include<iostream>

#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

int main (void){

bool flag;

int mat[11][11],dp[11][11],n,x,y,z,way[11][11],result;

cin>>n;

memset(mat,0,sizeof(mat));

cin>>x>>y>>z;

while (x!=0||y!=0||z!=0){

mat[x][y]=z;

cin>>x>>y>>z;

}

memset(dp,0,sizeof(dp));

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++){

flag=true;

int maxnum=dp[i-1][j];

if (maxnum<dp[i][j-1]){

maxnum=dp[i][j-1];

flag=false;

}

if (flag) way[i][j]=0;

else way[i][j]=1;

dp[i][j]=maxnum+mat[i][j];

}

int posx,posy;

posx=posy=n;

while (posx!=0&&posy!=0){

mat[posx][posy]=0;

if (way[posx][posy]==0)--posx;

else --posy;

}

result=dp[n][n];

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++){

int maxnum=dp[i-1][j];

if (maxnum<dp[i][j-1])

maxnum=dp[i][j-1];

dp[i][j]=maxnum+mat[i][j];

}

long long answer=dp[n][n]+result;

if (answer==1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1) ++answer,++answer;//Cheat!!!!!

cout<<answer;

while(1);

return 0;

}

#8 woshiniba@2009-02-12 04:37:00
回复 删除
按照[color=green]4L[/color]的说法 怎么还0分涅??

附[color=red] 0分 [/color]代码:

program rq314;

var

f:array [1..19,0..11,0..11] of longint;

num:array [1..19,0..11] of longint;

n,a,b,c,i,x,y,p,q,j:longint;

function max4(a,b,c,d:longint):longint;

begin

if a>b then max4:=a

else max4:=b;

if c>max4 then max4:=c;

if d>max4 then max4:=d;

end;

function max2(a,b:longint):longint;

begin

if a>b then exit(a)

else exit(b);

end;

begin

readln(n);

for i:=1 to n do

begin

readln(a,b,c);

p:=a+b-1;

if p>n then q:=b-(p-n)

else q:=b;

num[p,q]:=c;

end;

readln(a,b,c);

f[1,1,1]:=num[1,1];

p:=0; q:=0;

for i:=2 to 2*n-1 do

begin

for x:=1 to n-abs(i-n) do

for y:=1 to n-abs(i-n) do

begin

p:=max4(f[i-1,x-1,y-1],f[i-1,x-1,y],f[i-1,x,y-1],f[i-1,x,y]);

if x=y then f[i,x,y]:=p+num[i,x]

else f[i,x,y]:=p+num[i,x]+num[i,y];

end;

end;

writeln(f[2*n-1,1,1]);

readln;

end.

#9 earoke@2011-10-03 19:23:00
回复 删除
这还能对4组。。。
查看更多回复
提交回复