Steadily Growing Steam
#动态规划 #背包 #枚举
题目描述
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 t_i ti, the point number. In addition, each card has a value v i v_i vi.
Now Alice is playing this game with Bob. According to the skill of Alice’s role, she can have Bob display n n n cards from the top of the deck. After that, Bob must choose some cards from the n n n 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 S S S and another is T T T , S ∩ T = ∅ S\cap T=\emptyset S∩T=∅ and ∑ i ∈ S t i = ∑ j ∈ T t j \sum_{i\in S} t_i=\sum _{j\in T}t_j ∑i∈Sti=∑j∈Ttj (Note that S ∪ T = { 1 , 2 , ⋯ n } S\cup T = \{1,2,\cdots n\} S∪T={1,2,⋯n} is not necessary). Then, Alice gets all of the cards in set S S S and Bob gets the cards in set T T T.
However, according to the skill of Bob’s role, before choosing the two sets, he can choose at most k k k different cards and double their point numbers. In other words, he can choose a sequence { a 1 , a 2 , ⋯ , a r } , ( 1 ≤ a 1 ≤ a 2 ≤ ⋯ ≤ a r ≤ n , 0 ≤ r ≤ k ) \{a_1,a_2,\cdots,a_r\},\,(1\leq a_1 \leq a_2\leq\cdots \leq a_r\le n,\, 0\le r\le k) {a1,a2,⋯,ar},(1≤a1≤a2≤⋯≤ar≤n,0≤r≤k) and for each i ( 1 ≤ i ≤ r ) i\,(1\le i \le r) i(1≤i≤r) , change t a i t_{a_i} tai into 2 t a i 2t_{a_i} 2tai. After that he can continue choosing the two sets.
Alice and Bob are partners in this game. Now given the n n n 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 ∑ i ∈ S ∪ T v i \sum_{i\in S \cup T}v_i ∑i∈S∪Tvi among all valid schemes(choose cards to double their point numbers, then choose cards and split them into two sets S , T S,T S,T of the same point number sum) and output it.
输入格式
The first line contains two integers n ( 1 ≤ n ≤ 100 ) n\,(1\le n \le 100) n(1≤n≤100) and k ( 0 ≤ k ≤ n ) k\,(0\le k \le n) k(0≤k≤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 i+1 i+1 line contains two integers v i ( ∣ v i ∣ ≤ 1 0 9 ) v_i\,(|v_i|\le 10^9) vi(∣vi∣≤109) and t i ( 1 ≤ t i ≤ 13 ) t_i\,(1\le t_i \le 13) ti(1≤ti≤13), denoting the value and the point number of the i i i-th card, respectively.
输出格式
Output one line containing one integer, denoting the maximum sum of the value of the cards that Alice or Bob can get.
样例 #1
样例输入 #1
4 1
10 1
-5 3
5 1
6 1
样例输出 #1
21
解题思路
首先，这道题可以看做是一道背包题目，但是题目中的需要把物品分为两个堆，当两堆体积一样的时候才能取答案。
那么我们就可以把放入其中一个堆看作是体积为正，另一个堆表示体积为负。
而由于存在 k k k次翻倍操作，那么我们背包的体积需要扩大为 k ∗ N k*N k∗N。
那么，我们还需要枚举每个数是否需要翻倍体积，剩下的就是普通的 01 01 01背包操作了。
具体而言，我们设计状态 f i , j , k f_{i,j,k} fi,j,k表示选了前 i i i个物品，有 j j j个物品翻倍，容量为 k k k的最大价值。
因此，有以下转移方程：
{ f i , j , k = f i − 1 , j , k f i , j , k = max ( f i , j , k , f i − 1 , j , k − v i + w i ) f i , j , k = max ( f i , j , k , f i − 1 , j , k + v i + w i ) f i , j , k = max ( f i , j , k , f i − 1 , j − 1 , k − 2 ∗ v i + w i ) f i , j , k = max ( f i , j , k , f i − 1 , j − 1 , k + 2 ∗ v i + w i ) \begin{cases} f_{i,j,k} = f_{{i-1},j,k} \\ f_{i,j,k} = \max(f_{i,j,k},f_{i-1,j,k-v_i}+w_i) \\ f_{i,j,k} = \max(f_{i,j,k},f_{i-1,j,k+v_i}+w_i) \\ f_{i,j,k} = \max(f_{i,j,k},f_{i-1,j-1,k-2*v_i}+w_i) \\ f_{i,j,k} = \max(f_{i,j,k},f_{i-1,j-1,k+2*v_i}+w_i) \end{cases} ⎩ ⎨ ⎧fi,j,k=fi−1,j,kfi,j,k=max(fi,j,k,fi−1,j,k−vi+wi)fi,j,k=max(fi,j,k,fi−1,j,k+vi+wi)fi,j,k=max(fi,j,k,fi−1,j−1,k−2∗vi+wi)fi,j,k=max(fi,j,k,fi−1,j−1,k+2∗vi+wi)
分别代表：
1.
1.
1. 不选当前物品
2.
2.
2. 选当前物品，并且放入其中一个堆。
3.
3.
3. 选当前物品，并且放入另一个堆。
4.
4.
4. 选当前物品，翻倍放入其中一个堆 。
1.
1.
1. 选当前物品，翻倍放入另一个堆。
最终答案就是 max i = 1 i ≤ k f n , i , k 2 N \max_{i=1}^{i\leq k}f_{n,i,\frac{k}{2}N} maxi=1i≤kfn,i,2kN
代码
const int N = 100 + 10;
int f[N][N][N * 30];
void solve() {
int n, m;
cin >> n >> m;
vector<int>w(n + 1), v(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> w[i] >> v[i];
}
memset(f, -0x3f, sizeof f);
f[0][0][N * 13] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= 26 * N; ++k) {
//不选
f[i][j][k] = std::max(f[i][j][k], f[i - 1][j][k]);
//不翻倍
if (k - v[i] >= 0 && k - v[i] <= N * 26)
f[i][j][k] = std::max(f[i][j][k], f[i - 1][j][k - v[i]] + w[i]);
if (k + v[i] <= N * 26 && k - v[i] >= 0)
f[i][j][k] = std::max(f[i][j][k], f[i - 1][j][k + v[i]] + w[i]);
//翻倍
if (k - 2 * v[i] >= 0 && k - 2 * v[i] <= 26 * N && j > 0)
f[i][j][k] = std::max(f[i][j][k], f[i - 1][j - 1][k - 2 * v[i]] + w[i]);
if (k + 2 * v[i] <= N * 26 && k + 2 * v[i] >= 0 && j > 0)
f[i][j][k] = std::max(f[i][j][k], f[i - 1][j - 1][k + 2 * v[i]] + w[i]);
}
}
}
int res = -inf;
for (int i = 0; i <= m; ++i) {
res = std::max(res, f[n][i][N * 13]);
}
std::cout << res << "\n";
}
signed main() {
ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
};