讨论 / 《走卒》,哪里错了,请帮忙(悬赏)
jerryR1 2010-07-18 07:55:00
点我顶贴 收藏 删除
问题背景】

空闲之时,下局棋,未尝不好……

【问题描述】

一场恶战,浪子最后只剩下了一个卒。而对方,还有……这场战斗以失败告终。不过浪子突发其想,把一个卒放在一张N*M的棋盘上。每个格子都有个分值。卒每移动到一个格子,就要减少那个格子上的分值(先减再走)。假设卒刚开始只有T分,求出卒从左上角走到右下角所剩的最大分值。(为了简化问题,卒只能向左右或向下移动,最左端与最右端是不相连的。即卒在最某行最左端时,只能向右或向下移动;卒在最某行最右端时,只能向左或向下移动。)

当此时,某位同学把浪子喊去开唰(就是拿很多题目来……),浪子只好发到网上来求助。

输入格式

第1行,三个数:N,M,T(1≤N,M≤100,1≤T≤1000)。

接下来N行,每行M个数。第I行的第J个数A[I,J]表示这格的分值(0≤A[I,J]≤10)

输出格式

若卒走到右下角时,所剩的最大分值为正,那么输出所剩的最大分值。反之,则输出“DONOT HAVE MORE”(不包括引号)

这哪里错了?

状态: Unaccepted

测评机: Xeost[5]

得分: 70分

提交日期: 2009-7-6 17:59:00

有效耗时: 1062毫秒

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

测试结果2: 测试结果错误.错误结果为:406

正确结果应为:407

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

正确结果应为:477

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

测试结果5: 测试结果错误.错误结果为:584

正确结果应为:588

测试结果6: 通过本测试点|有效耗时156ms

测试结果7: 通过本测试点|有效耗时156ms

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

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

测试结果10: 通过本测试点|有效耗时62ms

var a:array[0..100,0..100] of longint;

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

begin

readln(n,m,t);

for i:=1 to n do

begin

for j:=1 to m do read(a[i,j]);

readln;

end;

for i:=1 to n do a[i,0]:=maxlongint;

for i:=1 to m do a[0,i]:=maxlongint;

for i:=1 to n do

for j:=1 to m do

begin

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

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

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

end;

if t-a[n,m]<0 then write(’DONOT HAVE MORE’)

else write(t-a[n,m]);

end.

#1 wish@2009-07-06 03:10:00
回复 删除
左右都可以走
#2 Mato完整版@2009-07-06 03:14:00
回复 删除
F[i, j]表示第i行最后停在第j列的最小权值。

DP:

F[i, j]=F[i-1, k] + S[i, k, j];

其中S[i, k, j]=∑A[i, x](k<=x<=j)

边界:F[1, i]=S[1, 1, i]。

#3 jerryR1@2009-07-06 03:51:00
回复 删除
望大牛点明,还是没有听懂,谢谢
#4 wish@2009-07-06 04:04:00
回复 删除
我给你写个 O(N^2) 的吧

F[i, j] 表示从左上角走到 i 行 j 列的最大值

dp 核心伪代码

for i <- 2 to N

F[i, 1] <- F[i - 1, 1]

 for j <- 1 to M

  F[i, j] <- max{F[i - 1, j], F[i, j - 1]} + A[i, j]

 for j <- M - 1 downto 1

  F[i, j] <- max(F[i, j], F[i, j + 1] + A[i, j]}

两个 j 的 for 循环分别表示向右走和向左走的情况

边界

F[1, i] = A[1, 1] + A[1, 2] + ... + A[1, i]

#5 bobcoc@2010-07-18 01:37:00
回复 删除
和我一样的错误,我怀疑是数据有问题,希望站长提供数据供测试

状态: Unaccepted

测评机: Xeost[5]

得分: 70分

提交日期: 2010-7-18 16:26:00

有效耗时: 391毫秒

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

测试结果2: 测试结果错误.错误结果为:406

正确结果应为:407

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

正确结果应为:477

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

测试结果5: 测试结果错误.错误结果为:584

正确结果应为:588

测试结果6: 通过本测试点|有效耗时63ms

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

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

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

测试结果10: 通过本测试点|有效耗时46ms

提交代码: view sourceprint?01.#include <iostream>

02.using namespace std;

03.int f[100][100];

04.int a[100][100];

05.int m,n,T;

06.int main()

07.{

08.

cin>>n>>m>>T;

09.

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

10.

for (int j=0;j<m;j++)

11.

cin>>a[i][j];

12.

f[0][0]=a[0][0];

13.

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

14.

{

15.

f[i][0]=f[i-1][0]+a[i][0];

16.

}

17.

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

18.

{

19.

f[0][i]=f[0][i-1]+a[0][i];

20.

}

21.

22.

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

23.

for (int j=1;j<m;j++)

24.

{

25.

f[i][j]=f[i-1][j];

26.

if (f[i][j]>f[i][j-1])

27.

f[i][j]=f[i][j-1];

28.

f[i][j]+=a[i][j];

29.

}

30.

T-=f[n-1][m-1];

31.

if (T>0)

32.

cout<<T;

33.

else

34.

cout<<"DONOT HAVE MORE";

35.

cout<<endl;

36.

return 0;

37.}

#6 863671241@2010-07-18 07:55:00
回复 删除
先从左往右扫描,再从右往左扫描

var

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

a,b:array[0..100,0..100]of longint;

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

begin

if x<y then min:=x else min:=y;

end;

begin

readln(n,m,t);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

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

for i:=2 to m do b[1,i]:=b[1,i-1]+a[1,i];

for i:=2 to n do b[i,1]:=b[i-1,1]+a[i,1];

for i:=2 to n do begin

for j:=2 to m do

b[i,j]:=a[i,j]+min(b[i-1,j],b[i,j-1]);

for j:=m-1 downto 1 do

if b[i,j]>a[i,j]+min(b[i-1,j],b[i,j+1])

then b[i,j]:=a[i,j]+min(b[i-1,j],b[i,j+1]);

end;

if t-b[n,m]<0 then write('DONOT HAVE MORE') else write(t-b[n,m]);

readln;

readln;

end.

查看更多回复
提交回复