吉比特第二题AC代码
#include <iostream>
#include <vector>
using namespace std ;
int Min(int a , int b){
return a > b ? b : a ;
}
int main(){
int n , m ;
while(cin >> n >> m){
vector<vector<int> > map(n , vector<int>(m , 0)) ;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
cin >> map[i][j] ;
}
}
vector<vector<int> > dp(n , vector<int>(m , 0)) ;
dp[n - 1][m - 1] = map[n - 1][m - 1] > 0 ? 0 : - map[n - 1][m - 1];
for(int i = m - 2 ; i >= 0 ; i--){ //初始化
if(map[n - 1][i] > 0){
if(map[n - 1][i] - dp[n - 1][i + 1] > 0){
dp[n - 1][i] = 0 ;
}
else{
dp[n - 1][i] = dp[n - 1][i + 1] - map[n - 1][i] ;
}
}
else if(map[n - 1][i] < 0){
dp[n - 1][i] = dp[n - 1][i + 1] + (-map[n - 1][i]) ;
}
}
for(int i = n - 2 ; i >= 0 ; i--){ //初始化
if(map[i][m - 1] > 0){
if(map[i][m - 1] - dp[i + 1][m - 1] > 0){
dp[i][m - 1] = 0 ;
}
else{
dp[i][m - 1] = dp[i + 1][m - 1] - map[i][m - 1] ;
}
}
else{
dp[i][m - 1] = dp[i + 1][m - 1] + (-map[i][m - 1]) ;
}
}
for(int i = n - 2 ; i >= 0 ; i--){ //DP
for(int j = m - 2 ; j >= 0 ; j--){
dp[i][j] = Min(dp[i + 1][j] , dp[i][j + 1]) ;
dp[i][j] = (map[i][j] - dp[i][j]) > 0 ? 0 : -(map[i][j] - dp[i][j]) ;
}
}
cout << dp[0][0] + 1 << endl ;
}
return 0;
}
#吉比特##C++工程师#