题目描述 Hello Kitty又一次来到花生地里摘花生,从左上角进入花生地,从右下角出去,只能向右或者向下,请问Hello Kitty应该沿着什么样的路线走,能够摘到的花生数量最多(假设花生地里没有任何2株的花生一样多,也不存在多条路线能够摘到一样多的花生的情况)? 比如输入: 2 2 1 2 3 4 应该输出:1-3-4,也就是按照1 3 4这三株数量的花生摘过去,能够摘到最多的花生! 输入描述
第一行是2个整数m和n(2=<m,n<=100),代表花生地有m行,n列花生! 后面m行,每行有n个整数代表了每行中,每株花生的数量 输出描述
输出Hello Kitty按照走过的路线中,摘到每株花生的数量 输入样例: 2 2 1 2 3 4 输出样例:1-3-4
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int A[n+114][m+114]= {};
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>A[i][j];
}
}
cout<<A[1][1];
int a=1,b=1;
while(a<n&&b<m) {
if(A[a+1][b]>=A[a][b+1]) {
if(a+1<=n) {
cout<<"-"<<A[a+1][b];
a++;
}
} else {
if(A[a][b+1]!=A[n][m]) {
if(b+1<=m) {
cout<<"-"<<A[a][b+1];
b++;
}
}
}
}
cout<<"-"<<A[n][m];
return 0 ;
}
(本人的PAC代码)