icpc-Shanghai

I -SanGuoSha

链接：https://ac.nowcoder.com/acm/contest/24872/I
来源：牛客网

Alice enjoys playing a card game called Steadily Growing Steam (as known as SGS).

In this game, each player will play different roles and have different skills. Players get cards from the deck and use them to play the game. Each card has a numeric label $t_i$, the point number. In addition, each card has a value $v_i$.

Now Alice is playing this game with Bob. According to the skill of Alice’s role, she can have Bob display nnn cards from the top of the deck. After that, Bob must choose some cards from the nnn cards and split the chosen cards into two sets that the sum of the cards’ point numbers in the two sets are equal. In other words, if one of the sets is SSS and another is T , $S\cap T=\emptyset$ and $\sum_{i\in S} t_i=\sum _{j\in T}t_j$​ (Note that $S\cup T = \{1,2,\cdots n\}$ is not necessary). Then, Alice gets all of the cards in set S and Bob gets the cards in set T.

However, according to the skill of Bob’s role, before choosing the two sets, he can choose at most k different cards and double their point numbers. In other words, he can choose a sequence $\{a_1,a_2,\cdots,a_r\},\,(1\le a_1<a_2<\cdots <a_r\le n,\, 0\le r\le k)$ and for each $i\,(1\le i \le r)$ , change $t_{a_i}$ into $2t_{a_i}$. After that he can continue choosing the two sets.

Alice and Bob are partners in this game. Now given the nnn cards from the deck, they want to know the maximum possible sum of the values of the cards they finally get. In other words, determine the maximum $\sum_{i\in S \cup T}v_i$ among all valid schemes(choose cards to double their point numbers, then choose cards and split them into two sets S, T of the same point number sum) and output it.

输入描述:

The first line contains two integers $n\,(1\le n \le 100)$and $k\,(0\le k \le n)$, denoting the number of the displayed cards and the maximum number of cards that Bob can choose to double their point numbers, respectively.

The i+1 line contains two integers $v_i\,(|v_i|\le 10^9)$ and $t_i\,(1\le t_i \le 13)$, denoting the value and the point number of the i-th card, respectively.

Code:

/**
 *    author:  subobo
 *    created: 29.11.2021
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  vector<int> v(n + 3), t(n + 3);
  for (int i = 1; i <= n; ++i) {
    int vi, ti;
    cin >> v[i] >> t[i];
  }
  constexpr long long inf = (long long) 2e18;
  vector<vector<vector<long long>>> dp(n + 3, vector<vector<long long>>(k + 3, vector<long long>(n * 26 + 3, -inf)));
  dp[0][0][n * 13] = 0;
  for (int a = 1; a <= n; ++a) { // 枚举n张牌
    for (int b = 0; b <= k; ++b) { // 枚举k个限制
      for (int c = 0; c < n * 26; ++c) { // 滚动枚举ti和
        if (dp[a - 1][b][c] > -inf) {
          long long st = dp[a - 1][b][c];
          dp[a][b][c] = max(dp[a][b][c], st);
          if (c - t[a] >= 0) {
            dp[a][b][c - t[a]] = max(dp[a][b][c - t[a]], st + v[a]);
          }
          if (c + t[a] <= n * 26) {
            dp[a][b][c + t[a]] = max(dp[a][b][c + t[a]], st + v[a]);
          }
          if (b >= k) {
            continue;
          }
          if ((c - (t[a] << 1)) >= 0) {
            dp[a][b + 1][c - (t[a] << 1)] = max(dp[a][b + 1][c - (t[a] << 1)], st + v[a]);
          }
          if ((c + (t[a] << 1)) <= n * 26) {
            dp[a][b + 1][c + (t[a] << 1)] = max(dp[a][b + 1][c + (t[a] << 1)], st + v[a]);
          }
        }
      }
    }
  }
  long long res = 0;
  for (int i = 0; i <= k; ++i) {
    res = max(res, dp[n][i][n * 13]);
  }
  cout << res << '\n';
  return 0;
}