11月4日, 2016 2,133 views次
Link
Problem
小雪与小可可正在玩一种数字游戏。他们准备了n卡片,每一张卡片上都有一个整数。游戏开始后,小雪会先选择一个不小于a且不大于b的整数t,并告诉小可可这个数字t是多少。之后小可可会挑出恰好k张卡片,并将这k张卡片上的数字相加,得到的和数记为m。
小雪希望t和m差的绝对值尽可能大,而小可可却希望t和m差的绝对值尽可能小。在游戏开始前,他们二人都知道n,a,b和k是多少,也知道每一张卡片上的数字是多少。在小雪决定了t的大小后,不能再修改,之后才由小可可挑选纸牌。
小雪希望知道,在二人都尝试最优策略的情况下,t和m差的绝对值最大可以有多大?
Analysis
首先遍历A~B设为x, 然后找出卡片能够凑出的最接近于x的数,求abs的最大值就是答案。
所以我们需要找出N张卡片中选K张能够凑出的所有数。思路是dp
dp[i][j]代表前i张卡片,选j张能够凑出的数,可以用一个bitset向量表示每个数能否凑出。转移的话,dp[i][j] = (dp[i-1][j-1] << c[i]) || dp[i-1][j],其中c[i]表示第i个数的值, (dp[i-1][j-1] << c[i])表示选择第i张卡,dp[i-1][j]表示不选。为了节省空间,可以使用滚动数组。
Code
#include <bits/stdc++.h> using namespace std; const int maxn = 310, inf = 0x3f3f3f3f; int N, K, A, B; int v[maxn]; bitset<76000> dp[maxn]; vector<int> ok; int main() { scanf("%d%d%d%d", &N, &K, &A, &B); for(int i = 1; i <= N; ++i) scanf("%d", v + i); dp[0][0] = 1; for(int i = 1; i <= N; ++i) { for(int j = K; j >= 1; --j) { dp[j] |= dp[j-1] << v[i]; } } for(int i = 0; i < 76000; ++i) if(dp[K][i]) ok.push_back(i); int ans = -1; for(int i = A; i <= B; ++i) { auto it = lower_bound(ok.begin(), ok.end(), i); int cur = inf; if(it != ok.end()) cur = min(cur, abs(i - *it)); if(it != ok.begin()) cur = min(cur, abs(i - *(--it))); ans = max(ans, cur); } printf("%d\n", ans); return 0; }