AtCoder Educational DP Contest
[於 Feb, 2020 完成]
這套從簡到難的 DP 題組，有不少經典題，很適合照順序刷。 開始刷了之後，才發現自己實力的不足，有幾題想了很久還是想不出來，只好去翻別人的解答。刷完發現 code 都不長，狀態也不難列，但轉移式都要想很久。
A. Frog 1
1#include<bits/stdc++.h>
2using namespace std;
3int main() {
4 int N; scanf("%d", &N);
5 int dp[2] = {}, a[2] = {};
6 scanf("%d%d", &a[1], &a[0]);
7 dp[0] = abs(a[1] - a[0]);
8 for (int i = 3; i <= N; i++) {
9 int x; scanf("%d",&x);
10 dp[i % 2] = min(dp[i % 2] + abs(x - a[i % 2]),
11 dp[(i + 1) % 2] + abs(x - a[(i + 1) % 2]));
12 a[i % 2] = x;
13 }
14 printf("%d\n", dp[N % 2]);
15 return 0;
16}B. Frog 2
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 100005
4int main() {
5 int n, k;
6 scanf("%d%d", &n, &k);
7 int a[maxn], dp[maxn];
8 for (int i = 1; i <= n; i++)
9 scanf("%d", &a[i]);
10 for (int i = 1; i <= n; i++) {
11 if (i <= k) dp[i] = abs(a[i] - a[1]);
12 else {
13 dp[i] = dp[i - 1] + abs(a[i] - a[i - 1]);
14 for (int j = 2; j <= k; j++)
15 dp[i] = min(dp[i],
16 dp[i - j] + abs(a[i] - a[i - j]));
17 }
18 }
19 printf("%d\n", dp[n]);
20 return 0;
21}C. Vacation
1#include<bits/stdc++.h>
2using namespace std;
3int main() {
4 int n; scanf("%d", &n);
5 int dp[2][3] = {};
6 for (int i = 1; i <= n; i++)
7 for (int j = 0; j < 3; j++) {
8 int x; scanf("%d",&x);
9 dp[i % 2][j] = x + max(dp[(i + 1) % 2][(j + 1) % 3],
10 dp[(i + 1) % 2][(j + 2) % 3]);
11 }
12 printf("%d\n", max(dp[n % 2][0],
13 max(dp[n % 2][1], dp[n % 2][2])));
14 return 0;
15}D. Knapsack 1
1#include<bits/stdc++.h>
2using namespace std;
3#define maxW 100005
4int main() {
5 int n, W; scanf("%d%d", &n, &W);
6 long long dp[maxW] = {};
7 for(int i = 0; i < n; i++) {
8 int w, v; scanf("%d%d", &w, &v);
9 for(int j = W; j >= w; j--)
10 dp[j] = max(dp[j], dp[j - w] + v);
11 }
12 printf("%lld\n", dp[W]);
13 return 0;
14}E. Knapsack 2
dp[j] 為價值為 j 需要的物品最低重量。
1#include<bits/stdc++.h>
2using namespace std;
3int main() {
4 int n, W;
5 scanf("%d%d", &n, &W);
6 int dp[100005] = {};
7 for (int i = 1; i < 100005; i++)
8 dp[i] = 1000000005;
9 for (int i = 0; i < n; i++) {
10 int v, w; scanf("%d%d", &w, &v);
11 for(int j = 100000; j >= v; j--)
12 dp[j] = min(dp[j], dp[j-v] + w);
13 }
14 for (int i = 100000; i >= 0; i--)
15 if (dp[i] <= W) {
16 printf("%d\n", i);
17 break;
18 }
19 return 0;
20}F. LCS
1#include<bits/stdc++.h>
2using namespace std;
3int dp[3005][3005];
4int p[3005][3005];
5int main() {
6 ios_base::sync_with_stdio(0), cin.tie(0);
7 string s,t; cin >> s >> t;
8 int lens = s.length(), lent = t.length();
9 for (int i = 1; i <= lens; i++) {
10 for (int j = 1; j <= lent; j++) {
11 if (s[i - 1] == t[j - 1]) {
12 dp[i][j] = dp[i - 1][j - 1] + 1;
13 p[i][j] = 1;
14 } else if (dp[i][j - 1] > dp[i - 1][j]) {
15 dp[i][j] = dp[i][j - 1];
16 p[i][j] = 2;
17 } else {
18 dp[i][j] = dp[i - 1][j];
19 p[i][j] = 3;
20 }
21 }
22 }
23 string ans = "";
24 int ni = lens, nj = lent;
25 while (ni && nj) {
26 if (p[ni][nj] == 1) {
27 ans = s[ni - 1] + ans;
28 ni--, nj--;
29 } else if (p[ni][nj] == 2) nj--;
30 else ni--;
31 }
32 cout << ans << "\n";
33 return 0;
34}G. Longest Path
類似拓樸排序的方式在 DAG（有向無環圖）上做 dp。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 100005
4int main() {
5 int n, m; scanf("%d%d", &n, &m);
6 int in[maxn] = {}, dp[maxn] = {};
7 vector<int> e[maxn];
8 for (int i = 0; i < m; i++) {
9 int a, b; scanf("%d%d", &a, &b);
10 e[a].push_back(b);
11 in[b]++;
12 }
13 queue<int> q;
14 for (int i = 1; i <= n; i++)
15 if (!in[i]) q.push(i);
16 while (!q.empty()) {
17 int u = q.front(); q.pop();
18 for (int uu: e[u]) {
19 in[uu]--;
20 dp[uu] = max(dp[uu], dp[u] + 1);
21 if (!in[uu]) q.push(uu);
22 }
23 }
24 int ans = 0;
25 for (int i = 1; i <= n; i++)
26 ans = max(ans, dp[i]);
27 printf("%d\n", ans);
28 return 0;
29}H. Grid 1
1#include<bits/stdc++.h>
2using namespace std;
3#define mod 1000000007
4int main() {
5 int h, w; scanf("%d%d", &h, &w);
6 int dp[1005] = {};
7 char c[1005];
8 for (int i = 1; i <= h; i++) {
9 scanf("%s", c + 1);
10 for (int j = 1; j <= w; j++)
11 if (c[j] == '#') dp[j] = 0;
12 else if (i == 1 && j == 1) dp[j] = 1;
13 else dp[j] = (dp[j] + dp[j - 1]) % mod;
14 }
15 printf("%d\n", dp[w]);
16 return 0;
17}I. Coins
機率的 dp，所以難得用到 double。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 3000
4int main() {
5 int n; scanf("%d", &n);
6 double dp[maxn] = {1.0};
7 for (int i = 1; i <= n; i++) {
8 double p; scanf("%lf", &p);
9 for (int j = min(i, n / 2); j > 0; j--)
10 dp[j] = dp[j] * (1 - p) + dp[j - 1] * p;
11 dp[0] = dp[0] * (1 - p);
12 }
13 double ans = 1;
14 for(int i = 0; i <= n / 2; i++)
15 ans -= dp[i];
16 printf("%.9f\n", ans);
17 return 0;
18}J. Sushi
i 為剩 3 個，j 為剩 2 個，k 為剩 1 個的盤子數量。
$$DP_{i,j,k} = 1 + \frac{(n-i-j-k) DP_{i,j,k} + i DP_{i-1,j+1,k} + j DP_{i,j-1,k+1} + k DP_{i,j,k-1}}{n}$$
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 305
4double dp[maxn][maxn][maxn];
5inline double dfs(int i, int j, int k, int n) {
6 if(i < 0 || j < 0 || k < 0) return 0;
7 if (dp[i][j][k] > -1) return dp[i][j][k];
8 return dp[i][j][k] = (i * dfs(i - 1, j + 1, k, n) +
9 j * dfs(i, j - 1, k + 1, n) +
10 k * dfs(i, j, k - 1, n) +
11 n) / (i + j + k);
12}
13int main() {
14 int n; scanf("%d", &n);
15 int cnt[4] = {};
16 for (int i = 0; i < n; i++) {
17 int x; cin >> x;
18 cnt[x]++;
19 }
20 for (int i = 0; i <= n; i++)
21 for (int j = 0; j <= n; j++)
22 for (int k = 0; k <= n; k++)
23 dp[i][j][k] = -10;
24 dp[0][0][0] = 0;
25 printf("%.9f\n", dfs(cnt[3], cnt[2], cnt[1], n));
26 return 0;
27}K. Stones
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 105
4#define maxk 100005
5int main() {
6 int n, k; scanf("%d%d", &n, &k);
7 int a[maxn];
8 bool dp[maxk] = {0};
9 for (int i = 0; i < n; i++)
10 scanf("%d", &a[i]);
11 for (int i = 0; i <= k; i++)
12 if(!dp[i])
13 for (int j = 0; j < n; j++)
14 if(i + a[j] <= k)
15 dp[i + a[j]] = true;
16 if (dp[k]) printf("First\n");
17 else printf("Second\n");
18 return 0;
19}L. Deque
第一次遇到這題是在 2019NCPC，當時思考了很久能不能 Greedy，後來才想到是 0-sum game。於是用了 minimax 的概念，設計出狀態。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long LL;
4int main() {
5 ios_base::sync_with_stdio(0), cin.tie(0);
6 int n; cin >> n;
7 vector<LL> v(n+2);
8 for (int i = 1; i <= n; i++) cin >> v[i];
9 vector<vector<LL> > dp(n + 2, vector<LL>(n + 2,0));
10 for (int len = 1; len <= n; len++)
11 for (int i = 1, j = len; j <= n; i++, j++)
12 if(len % 2 == n % 2)
13 dp[i][j] = max(dp[i + 1][j] + v[i],
14 dp[i][j - 1] + v[j]);
15 else
16 dp[i][j] = min(dp[i + 1][j] - v[i],
17 dp[i][j - 1] - v[j]);
18 cout << dp[1][n] << "\n";
19 return 0;
20}M. Candies
dp[i][j] 發到第 i 人剩下 j 顆糖的方法數，用滾動優化空間複雜度。
dp[i][j] = dp[i-1][j] + … + dp[i-1][j+a[i]]。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxk 100005
4#define maxn 105
5#define mod 1000000007
6int main() {
7 int n, k; scanf("%d%d", &n, &k);
8 int a[maxn], dp[2][maxk];
9 for (int i = 1; i <= n; i++)
10 scanf("%d", &a[i]);
11 dp[0][k] = 1;
12 for(int i = 1; i <= n; i++) {
13 int sum = 0;
14 for(int j = k; j >= 0; j--) {
15 sum = (sum + dp[(i + 1) & 1][j]) % mod;
16 if(j + a[i] + 1 <= k)
17 sum = (sum + mod
18 - dp[(i + 1) & 1][j + a[i] + 1]) % mod;
19 dp[i & 1][j] = sum;
20 }
21 }
22 printf("%d\n", dp[n & 1][0]);
23 return 0;
24}N. Slimes
dp[i][j] 為合併史萊姆 i ~ j 所需的最小 cost。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 405
4#define INF 100000000000000
5typedef long long LL;
6int main() {
7 int n; scanf("%d", &n);
8 int a[maxn];
9 for (int i = 1; i <= n; i++)
10 scanf("%d", &a[i]);
11 LL sum[maxn] = {};
12 LL dp[maxn][maxn] = {};
13 for (int i = 1; i <= n; i++)
14 sum[i] = sum[i - 1] + a[i];
15 for (int len = 2; len <= n ; len++)
16 for(int i = 1, j = i + len - 1; j <= n; i++, j++) {
17 dp[i][j] = INF;
18 for (int k = i; k < j; k++)
19 dp[i][j] = min(dp[i][j],
20 dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
21 }
22 printf("%lld\n", dp[1][n]);
23 return 0;
24}O. Matching
位元 dp。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 23
4#define maxm (1<<21)+5
5#define mod 1000000007
6int dp[maxm] = {1};
7int main() {
8 int n; scanf("%d", &n);
9 int a[maxn][maxn];
10 for (int i = 0; i < n; i++)
11 for (int j = 0; j < n; j++)
12 scanf("%d", &a[i][j]);
13 int M = (1 << n) - 1;
14 for (int j = 0; j <= M; j++) {
15 int i = __builtin_popcount(j) - 1;
16 for (int k = 0; k < n; k++)
17 if (j & (1 << k) && a[i][k])
18 dp[j] = (dp[j] + dp[j - (1 << k)]) % mod;
19 }
20 printf("%d\n", dp[M]);
21 return 0;
22}P. Independent Set
經典樹 dp。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 100005
4#define mod 1000000007
5vector<int> e[maxn];
6long long dp[maxn][2] = {};
7void dfs(int v, int p) {
8 dp[v][0] = dp[v][1] = 1;
9 for (int u : e[v]) {
10 if (u == p) continue;
11 dfs(u, v);
12 dp[v][0] = dp[v][0] * (dp[u][0] + dp[u][1]) % mod;
13 dp[v][1] = dp[v][1] * dp[u][0] % mod;
14 }
15}
16int main() {
17 int n; scanf("%d", &n);
18 for (int i = 1; i < n; i++) {
19 int a, b; scanf("%d%d", &a, &b);
20 e[a].push_back(b), e[b].push_back(a);
21 }
22 dfs(1, 0);
23 printf("%lld\n", (dp[1][1] + dp[1][0]) % mod);
24 return 0;
25}Q. Flowers
帶權最長遞增子序列（Weighted Longest Increasing Subsequence）。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 200005
4typedef long long LL;
5int main() {
6 int n; scanf("%d", &n);
7 int h[maxn], a[maxn];
8 for (int i = 0; i < n; i++) scanf("%d", &h[i]);
9 for (int i = 0; i < n; i++) scanf("%d", &a[i]);
10 map<int, LL> m; m[0] = 0;
11 for(int i = 0; i<n; i++) {
12 map<int,LL>::iterator iter, iter_tmp;
13 iter = m.lower_bound(h[i]);
14 iter--;
15 LL val = iter->second + a[i];
16 iter++;
17 while(iter != m.end() && iter->second <= val) {
18 iter_tmp = iter;
19 iter_tmp++;
20 m.erase(iter);
21 iter = iter_tmp;
22 }
23 m[h[i]] = val;
24 }
25 printf("%lld\n", m.rbegin()->second);
26 return 0;
27}R. Walk
矩陣快速冪。
1#include<bits/stdc++.h>
2using namespace std;
3#define maxn 55
4#define mod 1000000007
5typedef long long LL;
6struct matrix {
7 int sz;
8 int m[maxn][maxn];
9 matrix(){}
10 matrix(int n) : sz(n) { memset(m, 0, sizeof(m)); }
11 void operator = (const matrix &A) {
12 for (int i = 0; i < sz; i++)
13 for (int j = 0; j < sz; j++)
14 m[i][j] = A.m[i][j];
15 }
16 matrix operator*(const matrix &A) {
17 matrix B(sz);
18 for (int i = 0; i < sz; i++)
19 for (int j = 0; j < sz; j++) {
20 B.m[i][j] = 0;
21 for (int k = 0; k < sz; k++)
22 B.m[i][j] = ((LL)m[i][k] * A.m[k][j] % mod
23 + B.m[i][j]) % mod;
24 }
25 return B;
26 }
27};
28matrix pow(matrix A, LL k) {
29 matrix ans(A.sz);
30 for (int i = 0; i < A.sz; i++)
31 ans.m[i][i] = 1;
32 while (k) {
33 if (k & 1) ans = ans * A;
34 k >>= 1;
35 A = A * A;
36 }
37 return ans;
38}
39int main() {
40 int n;
41 LL k;
42 scanf("%d%lld", &n, &k);
43 matrix A(n);
44 for (int i = 0; i < n; i++)
45 for (int j = 0; j < n; j++)
46 scanf("%d", &A.m[i][j]);
47 matrix ans = pow(A, k);
48 int cnt = 0;
49 for (int i = 0; i < n; i++)
50 for (int j = 0; j < n; j++)
51 cnt = (cnt + ans.m[i][j]) % mod;
52 printf("%d\n", cnt);
53 return 0;
54}S. Digit Sum
dp[i][j][k]：到第 i 個字母，同餘 j 的方法數，k 代表前 i 位是否和 input 的前 i 位一致。
1#include<bits/stdc++.h>
2using namespace std;
3#define mod 1000000007
4int dp[2][102][2] = {};
5inline void add(int &a, int b) {
6 a = (a + b % mod) % mod;
7}
8int main() {
9 ios_base::sync_with_stdio(0);
10 cin.tie(0);
11 string s; int d;
12 cin >> s >> d;
13 int len = s.length();
14 dp[1][0][1] = 1;
15 for (int i = 0; i < len; i++) {
16 memset(dp[i & 1], 0, sizeof(dp[i & 1]));
17 for (int j = 0; j < d; j++)
18 for (int k = 0; k <= 9; k++)
19 if(k < s[i]-'0')
20 add(dp[i & 1][(j + k) % d][0],
21 dp[!(i & 1)][j][0]),
22 add(dp[i & 1][(j + k) % d][0],
23 dp[!(i & 1)][j][1]);
24 else if (k == s[i] - '0')
25 add(dp[i & 1][(j + k) % d][0],
26 dp[!(i & 1)][j][0]),
27 add(dp[i & 1][(j + k) % d][1],
28 dp[!(i & 1)][j][1]);
29 else
30 add(dp[i & 1][(j + k) % d][0],
31 dp[!(i & 1)][j][0]);
32 }
33 cout << (dp[!(len & 1)][0][0] +
34 dp[!(len & 1)][0][1] - 1 + mod) % mod << "\n";
35 return 0;
36}T. Permutation
dp[i][j] 定義為前 i + 1 個數字結尾為 j 的組合數為多少（1 ≤ j ≤ i + 1）。 前綴和加速到 O(n²)。
1#include<bits/stdc++.h>
2using namespace std;
3const int mod = 1000000007;
4int main() {
5 ios_base::sync_with_stdio(0),cin.tie(0);
6 int n;
7 string s;
8 cin >> n >> s;
9 vector<int> dp(n + 1, 0), sum(n + 1, 1);
10 dp[1] = 1, sum[0] = 0;
11 for (int i = 1; i < n; i++) {
12 for (int j = 1; j <= i + 1; j++) {
13 if (s[i - 1] == '>')
14 dp[j] = (sum[i] - sum[j - 1] + mod) % mod;
15 else
16 dp[j] = sum[j - 1];
17 }
18 for (int j = 1; j <= n; j++)
19 sum[j] = (sum[j - 1] + dp[j]) % mod;
20 }
21 cout << sum[n] << "\n";
22 return 0;
23}U. Grouping
學會枚舉子集的辦法了！！
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4int main() {
5 ios_base::sync_with_stdio(0), cin.tie(0);
6 int n; cin >> n;
7 vector<vector<int>> a(n, vector<int>(n));
8 for (int i = 0; i < n; i++)
9 for (int j = 0; j < n; j++)
10 cin >> a[i][j];
11 int m = (1 << n);
12 vector<ll> cnt(m), dp(m);
13 for (int s = 0; s < m; s++)
14 for (int i = 0; i < n; i++)
15 if (s & (1 << i))
16 for (int j = i; j < n; j++)
17 if (s & (1 << j))
18 cnt[s] += a[i][j];
19 for (int s = 0; s < m; s++)
20 for (int sub = s; sub > 0; sub = (sub - 1) & s)
21 dp[s] = max(dp[s], dp[s - sub] + cnt[sub]);
22 cout << dp[m - 1] << "\n";
23 return 0;
24}V. Subtree
參考 codeforces 這篇討論 才寫出來。
解法：（有根樹）。
- up/down[node] 是 node 以上/下的點塗黑的方法數。
- down 的不難算，直接 dfs 做樹 dp 就行了。
- up 需要用到 down 的結果，算如果取 parent，其他子樹 down 的方法數。
- +1 代表不取 parent。
- 最後各點的結果為 up * down。
- 算其他子樹的方法和，因為需要取 mod 且模數不為質數，故需要維護其前/後綴積。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4#define maxn 100005
5#define pb push_back
6int mod;
7vector<int> e[maxn];
8vector<ll> pre[maxn], suf[maxn];
9ll up[maxn], down[maxn];
10void dfs1(int u, int p) {
11 for (int uu : e[u])
12 if (uu != p) dfs1(uu, u);
13 for (int i = 0; i < e[u].size(); i++) {
14 int uu = e[u][i];
15 pre[u][i] = i ? pre[u][i-1] : 1;
16 if(uu != p)
17 pre[u][i] = pre[u][i] * (1 + down[uu]) % mod;
18 }
19 for (int i = e[u].size() - 1; i >= 0; i--) {
20 int uu = e[u][i];
21 suf[u][i] = (i < e[u].size() - 1) ? suf[u][i + 1] : 1;
22 if(uu != p)
23 suf[u][i] = suf[u][i] * (1 + down[uu]) % mod;
24 }
25 down[u] = suf[u][0];
26}
27void dfs2(int u, int p) {
28 for (int i = 0; i < e[u].size(); i++) {
29 int uu = e[u][i];
30 if (uu == p) continue;
31 ll cnt = up[u];
32 if(i)
33 cnt = cnt * pre[u][i - 1] % mod;
34 if(i + 1 < e[u].size())
35 cnt = cnt * suf[u][i + 1] % mod;
36 up[uu] = cnt + 1; // 1是不取par
37 dfs2(uu, u);
38 }
39}
40int main() {
41 ios_base::sync_with_stdio(0);
42 cin.tie(0);
43 int n; cin >> n >> mod;
44 for (int i = 1; i < n; i++) {
45 int a, b; cin >> a >> b;
46 e[a].pb(b), e[b].pb(a);
47 }
48 e[1].pb(0), up[1] = 1;
49 for (int i = 1; i <= n; i++) {
50 pre[i].resize(e[i].size());
51 suf[i].resize(e[i].size());
52 }
53 dfs1(1, 0), dfs2(1, 0);
54 for (int i = 1; i <= n; i++)
55 cout << down[i] * up[i] % mod << "\n";
56 return 0;
57}W. Intervals
- 題意： 給定 M (1 ≤ M ≤ 200000) 組 (l[i], r[i]) (1 ≤ l[i] ≤ r[i] ≤ N ≤ 200000) 和 a[i] (|a[i]| ≤ 1000000000)。 當 l[i] ~ r[i] 至少有一個 1 的 a[i] 分，問構造出長度 N 的 01 字串最高得幾分。
- 解法：
- 轉移式：dp[i] = max{ dp[j] + sum{a[k]} }, j < l[k] ≤ i ≤ r[k]
- 優化：區間加值線段樹維護最大值。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4typedef pair<int, ll> pil;
5#define ls i << 1
6#define rs i << 1 | 1
7class RangeUpdateSegmentTree {
8 private:
9 struct node {
10 int l, r;
11 ll x = 0, adt = 0;
12 };
13 vector<node> a;
14 void push(int i) {
15 if (a[i].adt) {
16 a[ls].adt += a[i].adt, a[rs].adt += a[i].adt;
17 a[ls].x += a[i].adt, a[rs].x += a[i].adt;
18 a[i].adt = 0;
19 }
20 }
21 void pull(int i) {
22 a[i].x = max(a[ls].x, a[rs].x);
23 }
24 void build(int l, int r, int i) {
25 a[i].l = l, a[i].r = r;
26 if (l == r) return;
27 int mid = (l + r) >> 1;
28 build(l, mid, ls), build(mid + 1, r, rs);
29 }
30 public:
31 RangeUpdateSegmentTree(int n) : a(n << 2) {
32 build(0, n, 1);
33 }
34 void add(int l, int r, ll val, int i = 1) {
35 if (a[i].l >= l && a[i].r <= r) {
36 a[i].x += val;
37 a[i].adt += val;
38 return;
39 }
40 push(i);
41 int mid = (a[i].l + a[i].r) >> 1;
42 if (l <= mid) add(l, r, val, ls);
43 if (r > mid) add(l, r, val, rs);
44 pull(i);
45 }
46 ll maxx(int l, int r, int i = 1) {
47 if (l <= a[i].l && a[i].r <= r) return a[i].x;
48 push(i);
49 ll ret = -9e18;
50 int mid = (a[i].l + a[i].r) >> 1;
51 if (l <= mid) ret = max(ret, maxx(l, r, ls));
52 if (r > mid) ret = max(ret, maxx(l, r, rs));
53 pull(i);
54 return ret;
55 }
56};
57int main() {
58 ios_base::sync_with_stdio(0);
59 cin.tie(0);
60 int n, m;
61 cin >> n >> m;
62 vector<ll> add(n + 1);
63 vector<vector<pil>> del(n + 1);
64 for (int i = 0; i < m; i++) {
65 int l, r; ll a;
66 cin >> l >> r >> a;
67 add[l] += a;
68 del[r].push_back(pil(l, a));
69 }
70 RangeUpdateSegmentTree ST(n + 1);
71 ll ans = 0;
72 for (int i = 1; i <= n; i++) {
73 ST.add(0, i - 1, add[i]);
74 ll tmp = ST.maxx(0, i - 1);
75 ans = max(ans, tmp);
76 ST.add(i, i, tmp);
77 for (pil p : del[i])
78 ST.add(0, p.first - 1, -p.second);
79 }
80 cout << ans << "\n";
81 return 0;
82}X. Tower
將 solidness 排序後，再做 dp。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long LL;
4typedef pair<int,int> pii;
5typedef pair<int,pii> box;
6#define s first
7#define w second.first
8#define v second.second
9#define maxn 1005
10#define maxs 20005
11int main() {
12 int n; scanf("%d",&n);
13 box b[maxn];
14 for(int i=0; i<n; i++){
15 scanf("%d%d%d", &b[i].w, &b[i].s, &b[i].v);
16 b[i].s += b[i].w;
17 }
18 sort(b, b + n);
19 LL dp[maxs] = {};
20 LL ans = 0;
21 for (int i = 0; i < n; i++) {
22 for (int j = b[i].s; j >= b[i].w; j--) {
23 dp[j] = max(dp[j], dp[j - b[i].w] + b[i].v);
24 ans = max(ans, dp[j]);
25 }
26 }
27 printf("%lld\n", ans);
28 return 0;
29}Y. Grid 2
如果沒有障礙物，答案會是 C(h - 1 + w - 1, h - 1)。 有障礙物，就將障礙物那格的答案扣掉 C(x[i] - x[j] + y[i] - y[j], x[i] - x[j]) 次。
1#include<bits/stdc++.h>
2using namespace std;
3typedef pair<int, int> pii;
4typedef long long ll;
5#define x first
6#define y second
7#define mod 1000000007
8#define LEN 200005
9ll frc[LEN], inv[LEN];
10ll modinv(ll a, ll p = mod) {
11 if (p == 1) return 0;
12 ll pp = p, y = 0, x = 1;
13 while (a > 1) {
14 ll q = a / p, t = p;
15 p = a % p, a = t, t = y, y = x - q * y, x = t;
16 }
17 if (x < 0) x += pp;
18 return x;
19}
20void init() {
21 frc[0] = frc[1] = inv[0] = inv[1] = 1;
22 for (int i = 2; i < LEN; i++) {
23 frc[i] = frc[i - 1] * i % mod;
24 inv[i] = modinv(frc[i]);
25 }
26}
27inline ll C(int a, int b) {
28 return frc[a + b] * inv[a] % mod * inv[b] % mod;
29}
30inline void sub(ll &a, ll b) {
31 a = (a - b % mod + mod) % mod;
32}
33int main() {
34 ios_base::sync_with_stdio(0);
35 cin.tie(0);
36 init();
37 int h, w, n;
38 cin >> h >> w >> n;
39 vector<pii> p(n);
40 for (int i = 0; i < n; i++)
41 cin >> p[i].x >> p[i].y;
42 sort(p.begin(), p.end());
43 p.push_back(pii(h, w));
44 vector<ll> dp(n + 1, 0);
45 for (int i = 0; i <= n; i++) {
46 dp[i] = C(p[i].x - 1, p[i].y - 1);
47 for (int j = 0; j < i; j++)
48 if (p[i].y >= p[j].y)
49 sub(dp[i], dp[j] * C(p[i].x - p[j].x, p[i].y - p[j].y));
50 }
51 cout << dp[n] << "\n";
52 return 0;
53}Z. Grid 3
h[i] 為遞增，故可斜率優化，總複雜度 O(N)。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4int main() {
5 ios_base::sync_with_stdio(0), cin.tie(0);
6 int n; ll C; cin >> n >> C;
7 vector<ll> h(n + 1);
8 for (int i = 1; i <= n; i++) cin >> h[i];
9 vector<ll> dp(n + 1);
10 deque<int> dq(1, 1);
11 auto X = [&](int i) {
12 return -2 * h[i];
13 };
14 auto Y = [&](int i) {
15 return h[i] * h[i] + dp[i];
16 };
17 auto F = [&](int i, int j) {
18 return h[i] * X(j) + Y(j) + C + h[i] * h[i];
19 };
20 auto cross = [](ll x1, ll y1, ll x2, ll y2) {
21 return x1 * y2 - x2 * y1;
22 };
23 for (int i = 2; i <= n; i++) {
24 while (dq.size() >= 2) {
25 if (F(i, dq[0]) >= F(i, dq[1]))
26 dq.pop_front();
27 else break;
28 }
29 dp[i] = F(i, dq[0]);
30 while (dq.size() >= 2) {
31 int j = dq.back(), k = dq[dq.size()-2];
32 if (cross(X(j)-X(k), Y(j)-Y(k), X(i)-X(j), Y(i)-Y(j)) >= 0)
33 dq.pop_back();
34 else break;
35 }
36 dq.push_back(i);
37 }
38 cout << dp[n] << "\n";
39 return 0;
40}