http://codeforces.com/contest/1303

D. Fill The Bag

 

题意：给出了一些物品，每个大小都为2的幂次，有一个已知大小的背包。每个物品可以分裂成两个大小都为原来一半的物品。问最少分裂几次能恰好装满背包？

贪心

从大到小遍历所有物品，如果能放下就直接放，否则判断如果剩下的物品能放满背包，这个物品就不要了。否则就分裂，再把得到的两个物品和其他的一起再继续判断。

如果大物品并不是必须的，那么用小物品分裂放满背包是比分裂大物品更优的。

显然还需要的物品的2进制分布是确定的，现在就是需要把每一位需要的都凑出来，而同样是为了凑出某一位，用大的至少比小的多分裂1次。并且用幂次拼出更大的幂次也不存在需要先分裂再拼的情况，且既然总和足够，任何一位一定都是能拼出来的。所以用小的一定更优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
long long t, s, n, m, x, ans;
int main() {
	cin >> t;
	while (t--) {
		cin >> n >> m;
		s = ans = 0;
		multiset<int, greater<int>> f;
		while (m--) cin >> x, s += x, f.insert(x);
		if (s < n) puts("-1");
		else {
			while (n) {
				m = *f.begin();
				f.erase(f.begin());
				if (m <= n) n -= m, s -= m;
				else if (s - m < n) ++ans, f.insert(m / 2), f.insert(m / 2);
				else s -= m;
			}
			cout << ans << endl;
		}
	}
}

 

E. Erase Subsequences

 

题意：有s，t两个字符串，每次操作可以从s串里拿出一个子序列，然后在原串里删掉，接到新串后，问能否在2次操作内拼出t串。

dp

显然需要枚举t串的分割线，分成两部分，再看两部分作为s的子序列能否共存。

假设两部分为 t1,t1

dp[i][j]dp[i][j] 表示到s串第 ii 位，拼完t1串第 jj 位，最长能拼出 t2 串第几位。

转移方程为

dp[i][j]=dp[i−1][j]dp[i][j]=dp[i][j−1]+1,(s[i]=t2[dp[i][j−1]])dp[i][j]=dp[i−1][j−1],(s[i]==t1[j])dp[i][j]=dp[i-1][j]\\ dp[i][j]=dp[i][j-1]+1,(s[i]=t2[dp[i][j-1]])\\ dp[i][j]=dp[i-1][j-1],(s[i]==t1[j])\\

第一种情况表示s第 ii 位啥都不干。

第二种表示用来拼在t2后面。

第三种表示用来接在t1后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int T, n, m;
char s[maxn], t1[maxn], t2[maxn], t[maxn];
int dp[410][410];
bool check() {
	for (int i = 0; i <= n; i++)for (int j = 0; j <= m; j++)dp[i][j] = -INF;
	int l1 = strlen(t1 + 1), l2 = strlen(t2 + 1);
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= l1; j++) {
			dp[i][j] = dp[i - 1][j];
			if (dp[i - 1][j] >= 0 && dp[i - 1][j] <= l2 && s[i] == t2[dp[i - 1][j] + 1])
				dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);
			if (s[i] == t1[j])
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
		}
	}
	return dp[n][l1] >= l2;
}
int main() {
	cin >> T;
	while (T--) {
		bool flg = 0;
		scanf("%s", s + 1);
		scanf("%s", t + 1);
		n = strlen(s + 1); m = strlen(t + 1);
		for (int i = 0; i < m; i++) {
			int j;
			for (j = 0; j <= i; j++)t1[j] = t[j];
			t1[j] = 0;
			for (j = i + 1; j <= m; j++)
				t2[j - i] = t[j];
			t2[j - i] = 0;
			if (check()) { flg = 1; break; }
		}
		puts(flg ? "YES" : "NO");
	}
	return 0;
}