https://atcoder.jp/contests/abc159

E - Dividing Chocolate

 

题意：一个黑白的网格，要求切成几块，每块白格个数不超过k，问最少切几刀。1≤H≤10,1≤W≤10001 \leq H \leq 10,1 \leq W \leq 1000

H这么小，显然是状压枚举，然后贪心地纵向切最少刀。

然后就是模拟题了。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, k;
char mz[20][1010];
int U[1010], D[1010], tot, cnt[1010];
int ans = INF;
int sum[20][1010];
bool check() {
	for (int i = 1; i <= tot; i++) {
		if (cnt[i] > k)return false;
	}
	return true;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {
		scanf(" %c", &mz[i][j]);
		sum[i][j] = mz[i][j] - '0';
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) {
			sum[i][j] += sum[i - 1][j];
		}
	}
	for (int i = 0; i < (1 << (n - 1)); i++) {
		int u = 1, d = 1;
		int tmp = 0;
		for (int j = 0; j < 10; j++) {
			if (i&(1 << j))tmp++;
		}
		tot = 0;
		while (u <= n) {
			for (; d < n && !(i&(1 << (d - 1))); d++);
			U[++tot] = u; D[tot] = d;
			u = d + 1;
			d = u;
		}
		bool flg = 1;
		for (int j = 1; j <= m; j++) {
			for (int c = 1; c <= tot; c++) {
				cnt[c] = sum[D[c]][j] - sum[U[c] - 1][j];
			}
			if (!check()) { flg = 0; break; }
		}
		if (!flg)continue;
		int l = 1, r = 1;
		while (l <= m) {
			for (int j = 1; j <= tot; j++)cnt[j] = 0;
			while (r <= m) {
				for (int j = 1; j <= tot; j++) {
					cnt[j] += sum[D[j]][r] - sum[U[j] - 1][r];
				}
				if (!check())break;
				r++;
			}
			l = r;
			tmp++;
		}
		ans = min(ans, tmp - 1);
	}
	cout << ans << endl;
	return 0;
}

 

F - Knapsack for All Segments

 

题意：给定数列 AA 和正整数 SS，定义 f(L,R)f(L,R) 表示 [L,R][L,R] 中和为 SS 的子序列的个数。求 ∑i=1n∑j=inf(i,j)\sum_{i=1}^n\sum_{j=i}^n f(i,j)，即所有区间的 ff 值之和。

dp

dp[i][j]dp[i][j] 表示所有以 ii 为右端点的区间的和为 jj 的子序列个数之和。

dp[i][j]=dp[i−1][j]dp[i][j+A[i]]+=dp[i−1][j]dp[i][A[i]]+=idp[i][j]=dp[i-1][j]\\ dp[i][j+A[i]]+=dp[i-1][j]\\ dp[i][A[i]]+=i\\

前2行都容易理解，第3行表示当右端点由 i−1i-1 变为 ii 时，每个区间和为 A[i]A[i] 的子序列个数都增多了一个：{A[i]}\{A[i]\}。所以增加的 ff 值之和就是以 ii 为右端点的区间的个数，就是 ii 。

最终答案就是以所有点为右端点的所有区间和为 SS 的子序列个数和，即 ∑i=1ndp[i][S]\sum_{i=1}^ndp[i][S]。

本题在于要把dp的概念从一个区间变为多个区间，把 dp[L][R][S]dp[L][R][S] 变为 dp[R][S]dp[R][S]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, s;
int a[3010]; 
ll dp[3010][3010], ans;
const ll mod = 998244353;
int main() {
	scanf("%d%d", &n, &s);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= s; j++)dp[i][j] = dp[i - 1][j];
		dp[i][a[i]] = (dp[i][a[i]] + i) % mod;
		for (int j = 0; j + a[i] <= s; j++)
			dp[i][j + a[i]] = (dp[i][j + a[i]] + dp[i - 1][j]) % mod;
		ans = (ans + dp[i][s]) % mod;
	}
	cout << ans << endl;
	return 0;
}