SHARE
TWEET

Untitled

a guest Dec 7th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector< vector<int> > le_tabuleiro()
  6. {
  7.     vector< vector< int > > tabuleiro(8, vector<int>(8, 0) );
  8.     for(int i = 0; i < 8; ++i)
  9.     {
  10.         for(int j = 0; j < 8; ++j)
  11.         {
  12.             cin >> tabuleiro[i][j];
  13.         }
  14.     }
  15.     return tabuleiro;
  16. }
  17.  
  18. vector< pair<int, int> > direcoes = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
  19.  
  20. // funcao auxiliar que checa se esta no tabuleiro
  21. bool valid(int i, int j) {
  22.     return (i >= 0 && i < 8 && j >= 0 && j < 8);
  23. }
  24.  
  25. template< typename T>
  26. int resolve( const T& consumo, const T& recompensa, const int Q) {
  27.     // vou armazenar tudo em uma matriz, e dizer que a resposta inicial eh -inf
  28.     constexpr int neg_inf = 0xc0c0c0c0;
  29.     int DP[Q + 1][8][8];
  30.     for(int i = 0; i < Q + 1; ++i) for(int j = 0; j < 8; ++j) for(int k = 0; k < 8; ++k) DP[i][j][k] = neg_inf;
  31.  
  32.     // o estado da minha programacao dinamica eh
  33.     // dp[X][i][j] = qual a pontuacao maxima que eu posso fazer,
  34.     // terminando na posicao (i, j) gastando exatamente X de combustível!
  35.  
  36.     DP[0][0][0] = recompensa[0][0]; // estou assumindo que se ficarmos parados em (0,0) ganhamos
  37.                                     // a recompensa de (0,0) sem pagar o consumo!
  38.    
  39.      
  40.     for(int gasto_total = 1; gasto_total <= Q; ++gasto_total)
  41.     {
  42.         // quero calcular DP[gasto_total][i][j]
  43.         for(int i = 0; i < 8; ++i)
  44.         {
  45.             for(int j = 0; j < 8; ++j)
  46.             {
  47.                 if( gasto_total > consumo[i][j] ) continue; // nao da pra ir pra celula (i, j), pq eh mto cara
  48.  
  49.                 // vamos olhar todos os vizinhos
  50.                 for( const auto& d : direcoes )
  51.                 {
  52.                     if( valid(i + d.first, j + d.second ) ) {
  53.                         if( DP[gasto_total - consumo[i][j]][i + d.first][j + d.second] != neg_inf )
  54.                         {
  55.                             DP[gasto_total][i][j] = max( DP[gasto_total][i][j],
  56.                                                          DP[gasto_total - consumo[i][j]][i + d.first][j + d.second] + recompensa[i][j] );
  57.                         }
  58.                     }    
  59.                 }
  60.             }
  61.         }
  62.     }
  63.    
  64.     int ans = 0;
  65.     for(int x = 0; x <= Q; ++x) ans = max( ans, DP[x][0][0] );
  66.    
  67.     // se ele manda usar todo o combustivel, ai ans precisa ser = dp[Q][0][0]
  68.     return ans;
  69. }
  70.  
  71. int main()
  72. {
  73.    
  74.     int Q;
  75.     cin >> Q;
  76.    
  77.     auto consumo = le_tabuleiro();
  78.     auto recompensa = le_tabuleiro();
  79.  
  80.     cout << resolve< vector< vector< int > > >(consumo, recompensa, Q) << endl;  
  81.  
  82.  
  83.     return 0;
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top