题目描述
设有n×m的方格图,每个方格中都有一个整数。
现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。
小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。
输入格式
第1行两个正整数 n,m。
接下来n行每行m个整数,依次代表每个方格中的整数。
输出格式
一个整数,表示小熊能取到的整数之和的最大值。
数据范围
对于20%的数据,n,m≤5。
对于40%的数据,n,m≤50。
对于70%的数据,n,m≤300。对于100%的数据,1≤n,m≤1000。
方格中整数绝对值不超过10000。
输入样例1:
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
输出样例1:
9
输入样例2:
2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2
输出样例2:
-10
样例2解释
按上述走法,取到的数之和为(−1)+(−1)+(−3)+(−2)+(−1)+(−2)=−10,可以证明为最大值。
因此,请注意,取到的数之和的最大值也可能是负数。
include[HTML_REMOVED]
define int long long
using namespace std;
int dp[1005][1005];
int s[1005][1005];
int x[1005][1005];
int n,m,a[1005][1005];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i){
for(int j=1;j<=m;j){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i)dp[i][1]=a[i][1]+dp[i-1][1];
for(int i=2;i<=m;i){
//cout<[HTML_REMOVED]=1;j–){
s[j][i]=max(s[j][i],s[j+1][i]+a[j][i]);
}
for(int j=2;j<=n;j++){
x[j][i]=max(x[j][i],x[j-1][i]+a[j][i]);
}
for(int j=n;j>=1;j–){
dp[j][i]=max(s[j][i],x[j][i]);
}
}
cout<<dp[n][m];
return 0;
}
好厉害哦,好厉害哦大聪明陈宜轩
陈宜轩菜
说的好说得妙,说得呱呱叫
菜就多练
菜就多练
菜就多练
菜就多练
菜就多练
菜就多练
陈宜轩菜
陈宜轩菜
菜
菜
菜
菜
菜
菜
菜
1
菜