B. 车轮战

题目描述

你将进行 \(N\) 场决斗。一开始你的战斗力为 \(s\)，咒术强度为 \(x\)。每次决斗之前你可以选择：

• 令 \(s\leftarrow s+x\)。
• 令 \(x\leftarrow x+1\)。

每次决斗，如果你的 \(s\ge f_i\)，则你赢得决斗。求最多能赢多少场决斗。

思路

我们可以发现，你最多会进行 \(80\) 次操作 \(2\)，因为如果你当前已经做了 \(80\) 次，那么接下来再做一次操作 \(2\)，则会损失至少 \(80\) 的战斗力，那么你又要用 \(80\) 次操作才能弥补回来，而此时战斗力已经至少有 \(80^2=6400>5000\)，所以不做这次操作也能达到这么多，已经能够赢得所有的决斗了。

由此，我们就知道至多会输 \(160\) 场，就是先做 \(80\) 次操作 \(2\)，再做 \(80\) 次操作 \(1\)。

我们令 \(dp_{i,j,k}\) 表示考虑前 \(i\) 场，当前 \(x=j\)，输了 \(k\) 场的最大 \(s\)。

时空复杂度均为 \(O(N\max\{f_i\})\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5001;

int t, n, s, x, a[MAXN], ans, dp[MAXN][81][161];

void Solve() {
  cin >> n >> s >> x;
  ans = 0;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j <= 75; ++j) {
      for(int k = 0; k <= 140; ++k) {
        dp[i][j][k] = -int(1e9);
      }
    }
  }
  dp[0][0][0] = s;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j <= 75; ++j) {
      for(int k = 0; k <= 140; ++k) {
        if(dp[i][j][k] < s) {
          continue;
        }
        if(j < 75 && k + (dp[i][j][k] < a[i + 1]) <= 160) {
          dp[i + 1][j + 1][k + (dp[i][j][k] < a[i + 1])] = max(dp[i + 1][j + 1][k + (dp[i][j][k] < a[i + 1])], dp[i][j][k]);
        }
        if(k + (dp[i][j][k] + j + x < a[i + 1]) <= 160) {
          dp[i + 1][j][k + (dp[i][j][k] + j + x < a[i + 1])] = max(dp[i + 1][j][k + (dp[i][j][k] + j + x < a[i + 1])], dp[i][j][k] + j + x);
        }
      }
    }
  }
  for(int i = 0; i <= 160; ++i) {
    for(int j = 0; j <= 75; ++j) {
      if(dp[n][j][i] >= s) {
        cout << n - i << "\n";
        return;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}