Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector< vector<int> > le_tabuleiro()
- {
- vector< vector< int > > tabuleiro(8, vector<int>(8, 0) );
- for(int i = 0; i < 8; ++i)
- {
- for(int j = 0; j < 8; ++j)
- {
- cin >> tabuleiro[i][j];
- }
- }
- return tabuleiro;
- }
- vector< pair<int, int> > direcoes = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
- // funcao auxiliar que checa se esta no tabuleiro
- bool valid(int i, int j) {
- return (i >= 0 && i < 8 && j >= 0 && j < 8);
- }
- template< typename T>
- int resolve( const T& consumo, const T& recompensa, const int Q) {
- // vou armazenar tudo em uma matriz, e dizer que a resposta inicial eh -inf
- constexpr int neg_inf = 0xc0c0c0c0;
- int DP[Q + 1][8][8];
- 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;
- // o estado da minha programacao dinamica eh
- // dp[X][i][j] = qual a pontuacao maxima que eu posso fazer,
- // terminando na posicao (i, j) gastando exatamente X de combustível!
- DP[0][0][0] = recompensa[0][0]; // estou assumindo que se ficarmos parados em (0,0) ganhamos
- // a recompensa de (0,0) sem pagar o consumo!
- for(int gasto_total = 1; gasto_total <= Q; ++gasto_total)
- {
- // quero calcular DP[gasto_total][i][j]
- for(int i = 0; i < 8; ++i)
- {
- for(int j = 0; j < 8; ++j)
- {
- if( gasto_total > consumo[i][j] ) continue; // nao da pra ir pra celula (i, j), pq eh mto cara
- // vamos olhar todos os vizinhos
- for( const auto& d : direcoes )
- {
- if( valid(i + d.first, j + d.second ) ) {
- if( DP[gasto_total - consumo[i][j]][i + d.first][j + d.second] != neg_inf )
- {
- DP[gasto_total][i][j] = max( DP[gasto_total][i][j],
- DP[gasto_total - consumo[i][j]][i + d.first][j + d.second] + recompensa[i][j] );
- }
- }
- }
- }
- }
- }
- int ans = 0;
- for(int x = 0; x <= Q; ++x) ans = max( ans, DP[x][0][0] );
- // se ele manda usar todo o combustivel, ai ans precisa ser = dp[Q][0][0]
- return ans;
- }
- int main()
- {
- int Q;
- cin >> Q;
- auto consumo = le_tabuleiro();
- auto recompensa = le_tabuleiro();
- cout << resolve< vector< vector< int > > >(consumo, recompensa, Q) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement