小花生

study & life record.

关于 dp 优化

发表于 分类于 ，

从三道题品品 dp 优化的思路。

机缘巧合下最近连做了很多 dp 的题，出现了一些巧妙的优化，放一起感受感受。
  • 观察转移式，循环 dp 数组的优化。
  • 观察转移式，改维护前缀和作为 dp 的优化。
  • 从最优子结构的角度考虑 dp 的优化。

Teleporting Takahashi 2

ABC-372 F Teleporting Takahashi 2.

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

constexpr int mod = 998244353;

void solve(){
    int n, m, k; cin >> n >> m >> k;
    vector<PII>adj;
    while(m--){
        int u, v; cin >> u >> v; u--, v--;
        adj.emplace_back(u, v);
        // u 指向 v, 即从 v 转移到 u
    }

    int cur = 0;
    vector<int>dp(n, 1);
    for(int i = 1; i <= k; i++){
        cur = (cur + 1) % n;
        vector<PII>adds;
        for(auto &[u, v] : adj){
            int uu = (u + cur) % n;
            int vv = (v + cur - 1 + n) % n;
            adds.emplace_back(uu, dp[vv]);
        }

        for(auto &[u, val] : adds){
            dp[u] = (dp[u] + val) % mod;
        }
    }
    cout << dp[cur] << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Multiplicity

Codeforces 1061C Multiplicity.

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
#include<bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<int>dp(n + 1); dp[0] = 1;
    for(int i = 1; i <= n; i++){
        vector<int>l, r;
        for(int p = 1; p <= i && p * p <= a[i]; p++){
            if(a[i] % p) continue;
            l.emplace_back(p);
            if(p * p != a[i] && a[i] / p <= i) r.emplace_back(a[i] / p);
        }
        for(auto &u : r){
            dp[u] += dp[u - 1];
            dp[u] %= mod;
        }
        for(auto it = l.rbegin(); it != l.rend(); it++){
            dp[*it] += dp[*it - 1];
            dp[*it] %= mod;
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + dp[i]) % mod;
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Game With Triangles: Season 2

Codeforces 2074G Game With Triangles: Season 2.

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
 
void solve(){
    int n; cin >> n;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
 
    vector<vector<int>>dp(n + 2, vector<int>(n + 2));
    for(int len = 3; len <= n; len++){
        for(int l = 1, r = len; r <= n; l++, r++){
            for(int i = l + 1; i < r; i++){
                dp[l][r] = max(dp[l][r], dp[l + 1][i - 1] + dp[i + 1][r - 1] + a[l] * a[i] * a[r]);
            }
            for(int i = l; i < r; i++){
                dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
            }
        }
    }	
    cout << dp[1][n] << '\n';
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}