Educational DP Contest A-J

作者: waaagh | 来源:发表于2020-08-20 16:50 被阅读0次

A - Frog 1
思路：dp[i]: 青蛙跳到i位置最小cost，则动规公式：dp[i] = min{dp[i-1]+|h_i-h_i-1|，注意
代码：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAXN = 10e5+10;

int N;
int h[MAXN];
int dp[MAXN];

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> h[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0; dp[2] = abs(h[1]-h[2]);
    for(int i=3; i<=N; i++) {
        dp[i] = min({dp[i], dp[i-1]+abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2])});
    }
    cout << dp[N] << endl;
    return 0;
}

B - Frog 2

思路：dp[i] = min{dp[i-j] + |h_i-h_j|}, 1<=j<=k
代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 10e5+10;

int N, K;
int h[MAXN];
int dp[MAXN];

int main() {
    cin >> N >> K;
    for(int i=1; i<=N; i++) {
        cin >> h[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=K; j++) {
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]));
        }
    }
    cout << dp[N] << endl;
    return 0;
}

C - Vacation

思路：dp[i][0]: 第i天选A获得的最大幸福值
dp[i][0] = max{dp[i-1][1], dp[i-1][2]}+A[i],
dp[i][1] = max{dp[i-1][0], dp[i-1][2]}+B[i],
dp[i][2] = max{dp[i-1][0], dp[i-1][1]}+C[i],
ans = max{dp[N][0], dp[N][1], dp[N][2]}.
代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+10;
using ll = long long;

int N;
int a[MAXN], b[MAXN], c[MAXN];
ll dp[MAXN][4];
int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=N; i++) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i];
    }
    ll ans = 0; 
    for(int i=0; i<3; i++) {
        ans = max(ans, dp[N][i]);
    }
    cout << ans << endl;
    return 0;
}

D - Knapsack 1

E - Knapsack 2

思路：两题都是经典背包问题，区别在于D的W<10⁵而E的W<10⁹。设dp[i][j]: 前i个物品占j重量能获得的最大价值，dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]]+v[i]}，发现dp[i][j]只跟dp[i-1]相关，因此可以去掉一维i把二维变一维。dp[j]:j重量所能获得的最大价值，dp[j] = max{dp[j], dp[j-w[i]]+v[i]}。但即便如此E还是会超时，因为W太大10⁹必定超时。观察V很小10³，因此可以循环V，dp[j]:j价值所能获得的最大重量，dp[j] = max{dp[j], dp[j-v[i]]+w[j]}，循环时判断如果dp[j]<W，记录ans=max(ans, j)的值。
D代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 110;
const int MAXW = 1e5+10;
using ll = long long;

struct item {
    int w, v;
};
item a[MAXN];
int N, W;
ll dp[MAXN][MAXW];
int main() {
    cin >> N >> W;
    for(int i=1; i<=N; i++) {
        cin >> a[i].w >> a[i].v;
    }
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=N; i++) {
        for(int j=0; j<=W; j++) {
            if(j-a[i].w<0) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i].w] + a[i].v);
        }
    }
    ll ans = 0;
    for(int j=1; j<=W; j++) {
        ans = max(ans, dp[N][j]);
    }
    cout << ans << endl;
    return 0;
}

E代码：

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 110;
const ll MAXW = 1e9+10;
const int MAXV = 1e5+10;
struct item {
    ll w, v;
};
item a[MAXN];
int N, W;
ll dp[MAXV];
int main() {
    cin >> N >> W;
    ll s = 0;
    for(int i=1; i<=N; i++) {
        cin >> a[i].w >> a[i].v;
        s += a[i].v;
    }
    ll ans = 0;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i=1; i<=N; i++) {
        for(ll j=s; j>=a[i].v; j--) {
            dp[j] = min(dp[j], dp[j-a[i].v] + a[i].w);
            if(dp[j]<=W) ans = max(ans, j);
        }
    }
    /*
    for(int j=s; j>=0; j--) {
        if(dp[j]<=W)
            ans = max(ans, j);
    }
    */
    cout << ans << endl;
    return 0;
}

F - LCS

思路：经典的最长公共子序列，dp[i][j]: S1前i个字串和S2前j个字串的最长公共子序列个数。
$dp[i][j] = \begin{cases} dp[i-1][j-1]+1& \text{S1[i]==S2[j]} \\ max\{dp[i-1][j], dp[i][j-1]\}& \text{else} \\ \end{cases}$
题目不是求lcs的数量，而是lcs的字串序列，因此需要辅助数组trace来记录操作结果。
代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 3010;
string s, t;
int trace[N][N];
int dp[N][N];

int main() {
    cin >> s >> t;
    int n = s.length();
    int m = t.length();

    for(int i=0; i<=n; i++) {
        dp[i][0] = 0;
    }
    for(int j=0; j<=m; j++) {
        dp[0][j] = 0;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(s[i-1]==t[j-1]) {
                trace[i][j] = 0;
                dp[i][j] = dp[i-1][j-1] + 1;
            }else {
                if(dp[i-1][j]>dp[i][j-1]) {
                    trace[i][j] = 1;
                    dp[i][j] = dp[i-1][j];
                }else {
                    trace[i][j] = 2;
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
    }
    string ans;
    while(n && m) {
//        printf("%d, %d : %d\n", n, m, trace[n][m]);
        if(trace[n][m] == 0) {
            ans.push_back(s[n-1]);
            --n; --m;
        }else if(trace[n][m] == 1) {
            --n;
        }else if(trace[n][m] == 2) {
            --m;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    
    return 0;
}
/*
// memorize dp
int lcs(int n, int m) {
    if(n==0 || m == 0) return 0;
    if(dp[n][m]) return dp[n][m];
    if(s[n-1] == t[m-1]) {
        trace[n][m] = 0;
        dp[n][m] = lcs(n-1, m-1)+1;
    }else {
        int a = lcs(n-1, m);
        int b = lcs(n, m-1);
//        printf("%d, %d : %d, %d\n", n, m, a, b);
        if(a>b) {
            dp[n][m] = a;
            trace[n][m] = 1;
        }else {
            dp[n][m] = b;
            trace[n][m] = 2;
        }
    }
    return dp[n][m];
}
int main() {
    cin >> s >> t;
    int n = s.length();
    int m = t.length();
    memset(dp, 0, sizeof(dp));
    lcs(n, m);
    string ans;
    while(n && m) {
//        printf("%d, %d : %d\n", n, m, trace[n][m]);
        if(trace[n][m] == 0) {
            ans.push_back(s[n-1]);
            --n; --m;
        }else if(trace[n][m] == 1) {
            --n;
        }else if(trace[n][m] == 2) {
            --m;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}
*/

G - Longest Path

思路：求图的最长路径，最先想到枚举每个顶点到其他顶点的路径，找最大值，时间复杂度O(N*M)，按照题目给的10⁵肯定超时。其实很容易想到枚举时必然有重复求解，可以用memorized DP方法降低复杂度，最终复杂度O(N+M)。
代码：

#include<bits/stdc++.h>
using namespace std;

using LL = long long;
const int MAXN = 100100;

int N, M;
vector<int> g[MAXN];
int ans;
int dp[MAXN];
int dfs(int v) {
    if(dp[v]) return dp[v];
    for(int u=0; u<g[v].size(); u++) {
        dp[v] = max(dp[v], dfs(g[v][u])+1);
    }
    return dp[v];
}
int main() {
    scanf("%d%d", &N, &M);
    for(int i=0; i<M; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
    }
    
    memset(dp, 0, sizeof(dp));
    ans = 0;
    for(int i=1; i<=N; i++) {
        ans = max(ans, dfs(i));
    }
    printf("%d\n", ans);
    return 0;
}

H - Grid 1

题目大意：求迷宫中从左上角到右下角路径个数。
思路：dp[x][y] = dp[x-1][y] + dp[x][y-1]
代码：

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define MAXH 1010
#define MAXW 1010
const int MOD = 1e9+7;

int H, W;
char g[MAXH][MAXW];

int dx[] = {1, 0};
int dy[] = {0, 1};
int dp[MAXH][MAXW];

void debug() {
    for(int i=1; i<=H; i++) {
        for(int j=1; j<=W; j++) {
            cout << dp[i][j];
        }
        cout << endl;
    }
}
int main() {
    cin >> H >> W;
    for(int i=1; i<=H; i++) {
        for(int j=1; j<=W; j++) {
            cin >> g[i][j];
        }
    }

    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=H; i++) {
        for(int j=1; j<=W; j++) {
            if(i==1&&j==1){
                dp[i][j] = 1;
                continue;
            }
            if(g[i][j] == '#')
                dp[i][j] = 0;
            else
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
        }
    }
    cout << dp[H][W] << endl;
//    debug();
    return 0;
}

I - Coins

思路：dp[i][j]: 掷前i个硬币有j个面朝上的概率，则dp[i][j] = dp[i-1][j-1]*p_j + dp[i-1][j]*(1-p_j)，最后 $\sum_{k=\lceil N/2 \rceil}^{N} {dp[N][k]}$ .
代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 3010;
using ll = long long;

int N;
double p[MAXN];
// dp[i][j]: 前i个硬币j个头朝上的概率
double dp[MAXN][MAXN];

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> p[i];
    }

    dp[0][0] = 1; 
    for(int i=1; i<=N; i++) {
        for(int j=0; j<=i; j++) {
            if(j) dp[i][j] += dp[i-1][j-1]*p[i];
            dp[i][j] += dp[i-1][j] * (1-p[i]);
        }
    }
    double ans = 0.0;
    for(int i=(N+1)/2; i<=N; i++) {
        ans += dp[N][i];
    }
    cout <<setprecision(10) << ans << endl;
    return 0;
}

J - Sushi

题目大意：有N个dishes，每个dish有1~3个sushi，求拿走所有sushi的操作期望值。
思路：dp状态的个数肯定不能选N，猜测3个状态x、y、z。x代表1个sushi的盘子个数，y代表2个sushi的盘子个数，z代表3个sushi的盘子个数，设dp(x, y, z)为当1个sushi的盘子有x个，2个sushi的盘子有y个，3个sushi的盘子有z个时操作期望值，则dp(x,y,z) = x/n * dp(x-1, y, z) + y/n * dp(x+1, y-1, z) + z/n * dp(x, y+1, z-1) + (n-x-y-z)/n * dp(x, y, z) + 1，共同项dp(x,y,z)移项后化简得到：dp(x,y,z)=x/(x+y+z)dp(x-1,y,z) + y/(x+y+z)dp(x+1,y-1,z) + z/(x+y+z)*dp(x,y+1,z-1) + n/(x+y+z)
代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 310;
int N;
int a[MAXN];
double dp[MAXN][MAXN][MAXN];

int cnt[4];

double solve(int x, int y, int z) {
    double ret;
    if(x==0 && y==0 && z==0) return 0;
    if(dp[x][y][z]>0.0) return dp[x][y][z];
    int sum = x+y+z;
    ret = 1.0*N/sum;
    if(x>0) {
        ret += 1.0*x/sum * solve(x-1, y, z);
    }
    if(y>0) {
        ret += 1.0*y/sum * solve(x+1, y-1, z);
    }
    if(z>0) {
        ret += 1.0*z/sum * solve(x, y+1, z-1);
    }
    return dp[x][y][z] = ret;
}
int main() {
    cin >> N;
    memset(cnt, 0, sizeof(cnt));
    for(int i=1; i<=N; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    cout <<fixed<<setprecision(14) <<solve(cnt[1], cnt[2], cnt[3]) << endl;
    return 0;
}

Educational DP Contest A-J

B - Frog 2

C - Vacation

D - Knapsack 1

E - Knapsack 2

F - LCS

G - Longest Path

H - Grid 1

I - Coins

J - Sushi

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员