EGG - Thả trứng , trò giải trí tuổi teen

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 1001;

using namespace std;

int dp[N][N], best[N][N];
int nTest;

void initialize() {
  //* dp[i][j] = i eggs, j floors
  FOR(i, 1, N) dp[1][i] = i;
  FOR(j, 1, N) {
    FOR(i, 2, N) {
      dp[i][j] = N;
      if (i > 3 && best[i - 1][j] == best[i - 2][j] && best[i - 2][j] == best[i - 3][j]) {
        int k = best[i][j] = best[i - 1][j];
        dp[i][j] = max(dp[i][j - k], dp[i - 1][k - 1]) + 1;
      } else {
        REP(k, 1, j) {
          int can = max(dp[i][j - k], dp[i - 1][k - 1]) + 1;
          if (dp[i][j] > can) {
            best[i][j] = k;
            dp[i][j] = can;
          }
        }
      }
    }
  }
}

void solve() {
  int x, y;
  while (nTest--) {
    cin >> x >> y;
    cout << dp[x][y] << endl;
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("EGG.in", "r", stdin);
    freopen("EGG.out", "w", stdout);
  #endif // _LAD_
  cin >> nTest;
  initialize();
  solve();
  return 0;
}

Download