hihocoder#1617:格子取数(dp)
7146 ワード
タイトルリンク:http://hihocoder.com/problemset/problem/1617
問題解:1本の繰返しのdp問題.この問題は明らかに2人が同時に起点から出発することを考慮することができて、このようにdp[step][i][j]を繰り返してstepのステップを歩いたことを表すことはできなくて、第1人は第i行の第2人は第j行の第数列でstepで減算すればいいです
そして、簡単なプッシュは、最初の人が必ず2番目の人の上にいることに注意して、重複しないことを確保します.
転載先:https://www.cnblogs.com/TnT2333333/p/7750054.html
問題解:1本の繰返しのdp問題.この問題は明らかに2人が同時に起点から出発することを考慮することができて、このようにdp[step][i][j]を繰り返してstepのステップを歩いたことを表すことはできなくて、第1人は第i行の第2人は第j行の第数列でstepで減算すればいいです
そして、簡単なプッシュは、最初の人が必ず2番目の人の上にいることに注意して、重複しないことを確保します.
#include
#include
#include
#define inf 0X3f3f3f3f
using namespace std;
int dp[2 * 233][233][233];
int a[233][233] , n;
bool Is(int step , int x , int y) {
int x1 = step - x , y1 = step - y;
return (x1 >= 0 && x1 < n && y1 >= 0 && y1 < n && x >= 0 && x < n && y >= 0 && y < n);
}
int get_val(int step , int x , int y) {
if(Is(step , x , y)) return dp[step][x][y];
return -inf;
}
int main() {
scanf("%d" , &n);
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
scanf("%d" , &a[i][j]);
dp[0][i][j] = -inf;
}
}
dp[0][0][0] = a[0][0];
for(int step = 1 ; step <= 2 * n - 2 ; step++) {
for(int i = 0 ; i < n ; i++) {
for(int j = i ; j < n ; j++) {
dp[step][i][j] = -inf;
if(!Is(step , i , j)) continue;
if(i != j) {
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i - 1 ,j - 1));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i - 1 , j));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i , j - 1));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i , j));
dp[step][i][j] += a[i][step - i] + a[j][step - j];
}
else {
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i - 1 , j - 1));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i - 1 , j));
dp[step][i][j] = max(dp[step][i][j] , get_val(step - 1 , i , j));
dp[step][i][j] += a[i][step - i];
// val 。
}
// , i>=j
}
}
}
printf("%d
" , dp[2 * n - 2][n - 1][n - 1] + a[0][0] + a[n - 1][n - 1]);
return 0;
}
転載先:https://www.cnblogs.com/TnT2333333/p/7750054.html