空闲之时,下局棋,未尝不好……
【问题描述】
一场恶战,浪子最后只剩下了一个卒。而对方,还有……这场战斗以失败告终。不过浪子突发其想,把一个卒放在一张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.
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]。
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]
状态: 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.}
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.