Problem #3281 - ECNU Online Judge

徐向宏

4 年，4 月前

var n,m,l,i,j:longint;
a:array[0..1000,0..1000] of int64;
function max(x,y:int64):int64;
begin
if x< y then
exit(y)
else
exit(x);
end;
begin
read(n,m,l);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;
a[1,1]:=l+a[1,1];
begin
for i:=1 to n do
for j:=1 to m do
begin
a[i,j]:=max(a[i-1,j],a[i,j-1])+a[i,j];
if a[i,j]< 0 then
a[i,j]:=-maxlongint;
end;
end;
if a[n,m]>=0 then
write(a[n,m])
else
write(-1);
end.
大佬求解

回复 0 0

10175101159

6 年，8 月前

很欣慰慢慢对dp有一点感觉（错觉）了
可以用mp表地图，dp初始为负再递推结果

#include<bits/stdc++.h>
using namespace std;
int m,n,h;
int mp[1001][1001];
int dp[1001][1001];
int i,j;
int main()
{
    cin>>m>>n>>h;
    memset(dp,0xff,sizeof(dp));
    dp[0][1]=dp[1][0]=h;
    for(i=1;i<=m;++i)for(j=1;j<=n;++j)cin>>mp[i][j];
    for(i=1;i<=m;++i)for(j=1;j<=n;++j){
        if(dp[i][j-1]>=0)
            dp[i][j]=max(dp[i][j],dp[i][j-1]+mp[i][j]);
        if(dp[i-1][j]>=0)
            dp[i][j]=max(dp[i][j],dp[i-1][j]+mp[i][j]);
    }
    cout<<max(dp[m][n],-1);
    return 0;
}

回复 0 0

10175102262 LarsPendragon

6 年，8 月前

注意：当某个点左侧和上方的“寿元”都小于0时，这个点是无法到达的。
附C++代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int maze[1001][1001];
    int x, y, l;
    const int impossible=-5000000;
    cin>>x>>y>>l;
    for(int i=0; i<=x; i++) maze[i][0]=-200;
    for(int j=0; j<=y; j++) maze[0][j]=-200;
    for(int i=1; i<=x; i++) for(int j=1; j<=y; j++) cin>>maze[i][j];
    maze[1][1]+=l;
    for(int i=1; i<=x; i++) for(int j=1; j<=y; j++)
    {
        if(i==1 && j==1) continue;
        else
        {
            if(maze[i-1][j]<0 && maze[i][j-1]<0) maze[i][j]=impossible;
            else maze[i][j]+=max(maze[i-1][j], maze[i][j-1]);
        }
    }
    if(maze[x][y]<0) cout<<-1<<endl;
    else cout<<maze[x][y]<<endl;
    return 0;
}

回复 0 0

3281. 找不到路哒 ultmaster

服务

开源

关于我们