BOJ 27163 - 벚꽃 내리는 시대에 결투를

BOJ 27163 - 벚꽃 내리는 시대에 결투를

고전한 문제이다.

은근히 Knapsack의 역추적이 어렵다.

Knapsack임은 보였는데 여러가지 처리해줄 조건들이 많다.

공식 해설 링크

---

우선 $-/Y$ 인 경우는 무조건 $L$ 을 그냥 깎아주면 된다.

모두 깎고 $L$이 $0$이하이면 불가능하다.

$X=0 \ \text{or}\ Y=0$ 인 경우도 따로 처리해서 그냥 무시하고 정답에 각각 $A$와 $L$ 을 미리 표시해두자.

나머지들은 새로운 배열에 옮겨담는다.

$DP[i][l]=i$ 번째 전 아이템까지 보고 라이프가 $l$ 남아있을 때 남은 오라의 최대값

이라고 두자.

처음에 모두 $-\infty$로 초기화해주고 $dp[1][L]=A$ 라고 두고 시작한다.

이제 각 아이템들을 $A$로 받느냐 $L$로 받느냐에 따라 이 DP테이블을 $O(n^2)$에 채워줄 수 있고, $dp[N+1]$ 에서 $-\infty$이 아닌 값이 있으면 가능하다고 판별할 수 있다.

이제 이걸 역추적하면 된다.

void solve() {
   int N, A, L;
   cin >> N >> A >> L;
   vector<array<int, 3>> a;
   string ans(N, 'A');
   for (int i = 0; i < N; i++) {
      int ad, ld;
      cin >> ad >> ld;

      if (ad == 0) {
         ans[i] = 'A';
         continue;
      }
      if (ld == 0) {
         ans[i] = 'L';
         continue;
      }

      if (ad == -1) {
         ans[i] = 'L';
         L -= ld;
      } else if (ld == -1) {
         ans[i] = 'A';
         a.pb({ad, ld, i});
      } else {
         a.pb({ad, ld, i});
      }
   }

   if (L <= 0) {
      cout << "NO";
      return;
   }

   N = sz(a);

   int asum = 0;

   // dp[i][l] = i 번째 전까지 보고 라이프 l이 남았을 때 남은 오라의 최대값
   vvi dp(N + 1, vi(L + 1, -1));

   dp[0][L] = A;

   vvi prev(N + 1, vi(L + 1));

   for (int i = 0; i < N; i++) {
      asum += a[i][0];
      for (int j = 0; j <= L; j++) {
         if (dp[i][j] == -1) continue;
         if (a[i][1] == -1) {
            dp[i + 1][j] = max(0ll, dp[i][j] - a[i][0]);
            prev[i][j] = 'A';
         } else {
            // i 번째를 A로 사용할 경우
            if (dp[i][j] >= a[i][0]) {
               dp[i + 1][j] = dp[i][j] - a[i][0];
               prev[i][j] = 'A';
            }
            // L로 사용할 경우
            if (j - a[i][1] >= 0) {
               if (dp[i + 1][j - a[i][1]] < dp[i][j]) {
                  dp[i + 1][j - a[i][1]] = dp[i][j];
                  prev[i][j - a[i][1]] = 'L';
               }
            }
         }
      }
   }
   debug(dp);
   dp[N][0] = -1;
   if (maxe(dp[N]) != -1) {
      cout << "YES\n";

      int ora = 0;
      int life = 0;

      for (int i = 1; i <= L; i++) {
         if (dp[N][i] != -1) {
            ora = dp[N][i];
            life = i;
            break;
         }
      }

      for (int i = N - 1; i >= 0; i--) {
         ans[a[i][2]] = prev[i][life];
         if (prev[i][life] == 'A') {

         } else {
            life += a[i][1];
         }
      }

      cout << ans;
   } else {
      cout << "NO";
   }
}