Atc Educational DP Contest

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 2.6k 阅读时长 ≈ 9 分钟
本文记录了atc Educational DP Contest的A-Z题

传送门

体现了Educational。感觉对于萌新（我）或者回顾回顾还是不错的。

A - Frog 1

Description

给定 $n$ 个石头,石头高度分别为$h_1…h_n$。现在要求小青蛙从 $1$ 号石头跳到 $n$ 号石头，每次小青蛙可以选择从 $i$ 号石头跳到 $i+1$ 或 $i+2$ 号石头，代价是起跳点与落点的高度差的绝对值。求最小代价。

Solution

暴力dp。

令 $dp[i]$ 表示小青蛙跳到第 $i$ 号石头时的最小代价。

Complexity: $O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
constexpr int maxn = 1e6+10;
int dp[maxn],a[maxn];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 2; i <= n; i++){
        if(i >= 3){
            dp[i] = min(dp[i-2]+abs(a[i]-a[i-2]),abs(a[i]-a[i-1])+dp[i-1]);
        }else {
            dp[i] = abs(a[i]-a[i-1])+dp[i];
        }
    }
    cout << dp[n] <<endl;
}

B - Frog 2

Description

给定 $n$ 个石头，第 $i$ 个石头的高度为 $h_i$ 。现要求小青蛙从 $1$ 号石头跳到 $n$ 号石头，每次小青蛙可以选择从 $i$ 号石头跳到 $i+t(1\le t\le k)$ 号石头，代价是起跳点与落点的高度差的绝对值。求最小代价。

Solution

暴力dp

设 $dp[i]$ 为小青蛙跳到第 $i$ 号石头时最小代价。

Complexity: $O(k*n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
constexpr int maxn = 1e6+10;
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9+7;
int n , k,a[maxn],dp[maxn];
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[1] = 0;
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(i-j<=0)continue;
            dp[i] = min(dp[i-j]+abs(a[i]-a[i-j]),dp[i]);
        }
    }
    /*for(int i = 1; i <=n ; i++){
        printf("dp[%d]===%d\n",i,dp[i]);
    }*/
    cout << dp[n] << endl;
}

C - Vacation

Description

Taro有 $n$ 天假期，每天他可以进行三种活动中的一种，每种活动给他带来的愉悦值各不相同。如果当天进行过某一种活动，第二天即不能进行另一种活动，求 $n$ 天后Taro能获得的最大愉悦值。

Solution

令 $dp[i][j]$ 分别记录在第 $i$ 天选做第 $j$ 件娱乐活动的最大愉悦值。

Complexity: $O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n , a[maxn], b[maxn], c[maxn], dp[maxn][3];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[1][1] = a[1],dp[1][2] = b[1],dp[1][3]=c[1];
    for(int i = 2; i <= n; i++){
        dp[i][1] = a[i]+max(dp[i-1][2],dp[i-1][3]);
        dp[i][3] = c[i]+max(dp[i-1][2],dp[i-1][1]);
        dp[i][2] = b[i]+max(dp[i-1][1],dp[i-1][3]);
    }
    cout << max(max(dp[n][1],dp[n][2]),dp[n][3]) <<endl;
}

D - Knapsack 1

Description

01背包板子题

Solution

设 $dp[i]$ 为背包重量不超过 $i$ 时候最大价值。
Complexity: $O(N*W)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int N , W, w[maxn],v[maxn],dp[105][100005];
int32_t main()
{
    cin >> N >> W;
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> v[i];
    }
    for(int i = 1; i <= N;i++){
        for(int j = 1; j <= W;j++){
            if(w[i] <= j){
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][W];
}

E - Knapsack 2

Description

$n$ 件物品，大小和权值分别为 $w_i$，$v_i$,给定背包最大容量$W$ ，$MAX$ 化价值。

Solution

由于 $W$ 很大，所以不能如同 D 题的做法，但是发现价值很小，对价值进行背包。求出来达到某一个权值最小的重量，然后找到满足限制的最大的价值即可。(因为，如果能达到权值比这个还大的点，那么这个点很显然也是可以达到的。)

令 $dp[i]$ 表示装填价值为 $i$ 的物品的最小权值。
Complexity: $O(N*v)$

Code

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
int v[maxn], w[maxn], dp[maxn], N , V;
int32_t main()
{
    cin >> N >> V;
    for(int i = 1; i <= N; i++){
        cin >> v[i] >> w[i];
    }
    memset(dp , 0x3f, sizeof dp);
    dp[0] = 0;
    int zz = 0;
    for(int i = 1; i <= N; i++){
        for(int j = zz + w[i]; j >= w[i]; j--){
            dp[j] = min(dp[j], dp[j-w[i]]+v[i]);
        }
        zz+=w[i];
    }
    for(int i = zz;  i>=0; i--){
        dp[i] = min(dp[i],dp[i+1]);
    }
    int ans = 0;
    // for(int i = 1; i<= V;i++){
    //     printf("dp[%lld]===%lld\n",i,dp[i]);
    // }
    while(dp[ans] <= V)ans++;
    cout << ans - 1;
}

F - LCS

Description

输出字符串$s,t$的最长公共子串。

Solution

令 $dp[i][j]$ 表示 $s$ 的长度为 $i$ 的前缀和 $t$ 的长度为 $j$ 的前缀的最长公共子串。

自底向上输出这个串。

Complexity: $O(n^2)$

Code

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
#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a, b, t = "";
    cin >> a >> b;
    for (int i = 1; i <= a.size(); i++)
        for (int j = 1; j <= b.size(); j++)
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    int i = a.size(), j = b.size();
    while (dp[i][j])
    {
        if (dp[i][j] == dp[i - 1][j])
            i--;
        else if (dp[i][j] == dp[i][j - 1])
            j--;
        else if (dp[i][j] > dp[i - 1][j - 1])
            i--, j--, t += a[i];
    }
    reverse(t.begin(), t.end());
    cout << t;
}

G - Longest Path

Description

求 DAG 上的最长路径。

Solution

DAG上 dp。
Complexity: $O(n)$

Code

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
const int N = 1e6+100;
int n , m , x , y ,dp[N], deg[N];
vector<int > G[N];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m ; i++){
        cin >> x >> y;
        deg[y]++;G[x].pb(y);
    }
    queue<int > q ;
    for(int i = 1; i <= n; i++){
        if(!deg[i])q.push(i);
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        // cout << "now === " << now << endl;
        /*for(int it = 0; it < G[now].size(); it++){
            dp[G[now][it]] = max(dp[now]+1, dp[G[now][it]]);
            deg[G[now][it]]--;
            if(!deg[G[now][it]])q.push(G[now][it]);
            // cout << "it ==" <<  it << endl;
        }*/
        for(auto it : G[now]){
            dp[it] = max(dp[it] , dp[now]+1);
            deg[it] --;
            if(!deg[it])q.push(it);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(dp[i], ans);
    }cout << ans << endl;
    return 0;
}

按照 $DFS$ 序，$f[i]$ 表示从 $i$ 号点出发的最长路径上点的数量。

Complexity: $O(n)$

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 N 100001
#define M 100001
int hd[N], nx[M], e[M];
int f[N], v[N], n, m;
int dfs(int x) {
    if (f[x]) return f[x];
    for (int i = hd[x]; i; i = nx[i]) f[x] = max(f[x], dfs(e[i]));
    return ++f[x];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, Num = 0, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        nx[++Num] = hd[x], hd[x] = Num, e[Num] = y;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dfs(i));
    printf("%d\n", ans - 1);
    return 0;
}

H - Grid 1

Description

给定一个 $H，W$ 的网格，每次$(i,j)$可以到达$(i+1,j)$或者$(i),j+1$，有一些障碍。求从$(1,1)$到达$(H,W)$ 的方案数。

Solution

暴力dp

设$dp[i][j]$表示从$(1,1)$到达$(i,j)$的移动方案。

Complexity: $O(H\times W)$

Code

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

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 1e3 + 100;
const int mod = 1e9 + 7;
int h, w;
char a[N][N];
int dp[N][N];
bool check(int x, int y){
    if(x <= h && y <= w && x >= 1 && y >= 1)return true;
    return false;
}
int main()
{
    cin >> h >> w;
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cin >> a[i][j];
        }
    }
    dp[1][1] = 1;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(a[i][j] == '.'){
                if(check(i-1,j) && a[i-1][j] == '.'){
                    dp[i][j] += dp[i-1][j];
                    dp[i][j] %= mod;
                }
                if(check(i,j-1) && a[i][j-1] == '.'){
                    dp[i][j] += dp[i][j-1];
                    dp[i][j] %= mod;
                }
            }else dp[i][j] = 0;
        }
    }
    cout << dp[h][w];
    return 0;
}

I - Coins

Description

给定 $n(is \ odd)$ 个硬币，扔第 $i$ 个硬币时，它正面朝上的概率为 $p_i$ 。
求每一个硬币扔一次，正面朝上的数量多余反面朝上的硬币的数量的概率。

Solution

概率DP，记有 $i$ 个正面朝上的概率

Complexity: $O(n^2)$

Code

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

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 1e6+100;
int n ;
double p[N], dp[N];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    dp[0] = 1.0;
    for(int i = 1; i <= n; i++){
        for(int j = i; j >= 1; j--){
            dp[j] = (dp[j] * (1.0-p[i]) + dp[j-1]*p[i]);
        }
        dp[0] *= 1.0 - p[i];
    }
    /*for(int i = 1; i <= n; i++){
        printf("%.6f\n",dp[i]);
    }*/
    double ans = 0.0;
    for(int i = n/2 + 1; i <= n; i++){
        ans += dp[i];
    }
    printf("%.10f",ans);
    return 0;
}

J - Sushi

Description

有$n$个盘子，每盘里有 1到 3份食物。每次随机选中一份食物，若该盘中有食物，则吃掉一份。

求期望选择次数。

Solution

期望问题。
记忆化搜索。
设$dp[i][j][k]$为有 i 盘一份食物， j 盘二份食物， k 盘三份食物的期望选择次数。
Complexity: $O(n^3)$?? dont know

Code

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

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 310;
int a[4], x, n;
double dp[N][N][N];
double dfs(int i, int j, int k) {
    if (dp[i][j][k]) return dp[i][j][k];
    if (i + j + k == 0) return 0;
    /*double ans = 1;  //ok as well
    if(i) ans += dfs(i - 1, j , k) * i / n;
    if(j) ans += dfs(i + 1, j - 1, k) * j / n;
    if(k) ans += dfs(i , j+1 , k-1) * k / n;
    if(i+j+k!=n)ans*=1.0*n/(j+k+i);*/
    double ans = 1.0 * n / (i + j + k);
    if (i) ans += dfs(i - 1, j, k) * i / (i + j + k);
    if (j) ans += dfs(i + 1, j - 1, k) * j / (i + j + k);
    if (k) ans += dfs(i, j + 1, k - 1) * k / (i + j + k);
    return dp[i][j][k] = ans;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        a[x]++;
    }
    printf("%.10f", dfs(a[1], a[2], a[3]));
    return 0;
}

K - Stones

Description

给定 $n,k$ ,和集合 $\mathbb{A}$,$a_i\in\mathbb{A}$,总共$k$个石子，每次在集合 $\mathbb{A}$ 可取石 $x$,无法取石子的为输。问赢家是谁。

Solution

博弈结论。
设 $dp[i]$ 为先手的胜负状态。 胜负 局面 转移一下就行了。

Code

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

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 1e6+100;
int n , k , a[N], dp[N];
int boyi(int x){
    if(dp[x]) return dp[x];
    int fl = 0;
    for(int i = 0 ; i < n; i++){
        if(a[i] <= x && boyi(x - a[i]) == -1){
            fl = 1;
        }
    }
    return dp[x] =  (fl ? 1 : -1);
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    dp[0] = -1;
    puts(boyi(k) == 1? "First":"Second");
    return 0;
}

L - Deque

Description

给定一个序列 $a$ ，alice和bob轮流进行博弈，太郎先行。

每次可以从序列的两端中任取一端，删去那一段的第一个元素，并获取等量的分数。

alice 和 bob 都希望能最大化自己与对面的得分差，询问你最终 alice 与 bob 的得分差。

Solution

设 $dp[i][j]$表示剩余区间为 $[i,j]$ 时候的最大得分差。

状态转移方程为：$dp[l][r] = max(a[l] - dp[l+1][r], a[r]-dp[l][r-1] );$

取减号是因为：上一个人的负值是下一个人的正值。

Complexity: $O(n^2)$

Code

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

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 3e3+100;
ll dp[N][N];
int a[N], n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i ; j <= n; j++){//[j-i+1,j]
            int l = j - i + 1, r = j;
            dp[l][r] = max(a[l] - dp[l+1][r], a[r]-dp[l][r-1] ); // 上一个人的负值是下一个人的正值。
        }
    }
    cout << dp[1][n] <<endl;
    return 0;
}

M - Candies

Description

有 $n$ 个小朋友的需求，第 $i$ 个小朋友的需求为 $a_i$ ，表示他可以接受 $[0,a_i]$ 个糖果。
给定 $m$ 个糖果，把这些糖果全部分配出去，求有多少种分配方案。

Solution

设$dp[i][j]$为分配前 $i$ 个小朋友还剩 $j$ 个糖果的方案数。

Complexity: $O(n*k)$

Code

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
#include <bits/stdc++.h>
#define LL long long
#define PB push_back
#define POP pop_back()
#define PII pair<int, int>
#define ULL unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1), eps = 1e-10;
const int maxn = 1 << 17;
const int N = 1e2 + 10, M = 1e5 + 100;
const int mod = 1e9 + 7;
int dp[N][M], sum[N][M], n, k, a[N];
// dp[i][j] 表示到第i个人剩下j的数量
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dp[0][k] = sum[0][k] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = (sum[i - 1][min(k, j + a[i])] - sum[i - 1][j - 1] + mod) % mod;
        }
        sum[i][0] = dp[i][0] = sum[i - 1][a[i]];
        for (int j = 1; j <= k; j++)
        {
            sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;
        }
    }
    cout << dp[n][0] << endl;
}

N - Slimes

Description

Solution

Code

O - Matching

Description

Solution

Code

P - Independent Set

Description

Solution

Code

R - Walk

Description

Solution

Code

S - Digit Sum

Description

Solution

Code

T - Permutation

Description

Solution

Code

U - Grouping

Description

Solution

Code

V - Subtree

Description

Solution

Code

W - Intervals

Description

Solution

Code

X - Tower

Description

Solution

Code

Y - Grid 2

Description

Solution

Code

Z - Frog 3

Description

Solution

Code

-------------本文结束感谢您的阅读-------------