Atcoder-dp专练

A - Frog 1

O(n)

/*
dp[i]表示跳到i的最小花费
dp[i] = min(dp[i - 1] + | h[i| - h[i - 1] |, dp[i - 2] + | h[i] - h[i - 2] |)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n;
int a[MAXN], dp[MAXN];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], dp[i] = inf;
    dp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (i - 1 > 0)
            dp[i] = min(dp[i], dp[i - 1] + abs(a[i] - a[i - 1]));
        if (i - 2 > 0)
            dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]));
    }
    cout << dp[n];
    return 0;
}

B - Frog 2

O(nk)

/*
dp[i]表示跳到i的最小花费
dp[i] = min(dp[k] + | a[i] - a[k] |)
k表示能跳到i的位置
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, k;
int a[MAXN], dp[MAXN];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], dp[i] = inf;
    dp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        for (int j = i - 1; j >= i - k && j >= 1; j--)
            dp[i] = min(dp[i], dp[j] + abs(a[i] - a[j]));
    }
    cout << dp[n];
    return 0;
}

C - Vacation

O(n)

/*
dp[i][j]表示第i天做第j件事能够获得的最大收益
dp[i][j] = max(dp[i - 1][k] + a[i][j])(j != k)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n;
int a[MAXN][5], dp[MAXN][5];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 3; j++)
            cin >> a[i][j], dp[i][j] = -1;
    dp[1][1] = a[1][1], dp[1][2] = a[1][2], dp[1][3] = a[1][3];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                if (j != k)
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i][j]);
    cout << max({dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}

D - Knapsack 1

/*
01背包
dp[v]表示背包容量剩余v的时候能装载的最大价值
dp[v] = max(dp[v - weg[i]] + val[i])
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, Weg;
int weg[MAXN];
ll val[MAXN], dp[MAXN];
int main()
{
    cin >> n >> Weg;
    for (int i = 1; i <= n; i++)
        cin >> weg[i] >> val[i];
    for (int j = 1; j <= n; j++)
    {
        for (int i = Weg; i >= weg[j]; i--)
        {
            dp[i] = max(dp[i], dp[i - weg[j]] + val[j]);
        }
    }
    ll ans = 0;
    for (int i = 0; i <= Weg; i++)
        ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}

E - Knapsack 2

/*
01背包变形
dp[v]表示获得价值为v的物品所需要的最小容量
dp[v] = min(dp[v - val[i]] + weg[i])
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, Weg, sum = 0;
ll weg[MAXN], dp[MAXN];
int val[MAXN];
int main()
{
    cin >> n >> Weg;
    memset(dp, inf, sizeof(dp));
    for (int i = 1; i <= n; i++)
    {
        cin >> weg[i] >> val[i];
        sum += val[i];
    }
    dp[0] = 0;
    for (int j = 1; j <= n; j++)
    {
        for (int i = sum; i >= 0; i--)
        {
            dp[i] = min(dp[i], dp[i - val[j]] + weg[j]);
        }
    }
    for (int i = sum; i >= 0; i--)
        if (Weg >= dp[i])
        {
            cout << i;
            break;
        }
    return 0;
}

F - LCS

/*
dp[i][j]表示到a串第i个b串第j个所能构成的LCS
dp[i][j]=1)a[i]=b[j],dp[i][j]=dp[i-1][j-1]+1.2)dp[i][j]=max(dp[i][j],dp[i-1][j],dp[i][j-1])
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e3 + 3;
const int inf = 0x3f3f3f3f;
char a[MAXN], b[MAXN];
int dp[MAXN][MAXN], path[MAXN][MAXN];
void PrintLCS(int i, int j)
{
    if (!i || !j)
        return;
    if (path[i][j] == 1)
    {
        PrintLCS(i - 1, j - 1);
        putchar(a[i]);
    }
    else if (path[i][j] == 2)
        PrintLCS(i - 1, j);
    else
        PrintLCS(i, j - 1);
}
int main()
{
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int lena = strlen(a + 1);
    int lenb = strlen(b + 1);
    int ans = 0;
    for (int i = 1; i <= lena; i++)
        for (int j = 1; j <= lenb; j++)
            if (a[i] == b[j])
                dp[i][j] = dp[i - 1][j - 1] + 1, path[i][j] = 1;
            else if (dp[i - 1][j] >= dp[i][j - 1])
                dp[i][j] = dp[i - 1][j], path[i][j] = 2;
            else
                dp[i][j] = dp[i][j - 1], path[i][j] = 3;
    PrintLCS(lena, lenb);
    return 0;
}

G - Longest Path

/*
dp[i]表示从i点出发能到达的最长路
dp[i] = max(dp[j] + w[i, j])
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 3;
const int inf = 0x3f3f3f3f;
int n, m, ecnt = 0;
int deg[MAXN], fir[MAXN];
int dp[MAXN];
struct EDGE
{
    int v, nxt;
} edge[MAXN];
void addedge(int u, int v)
{
    deg[v]++;
    edge[ecnt].v = v;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
vector<int> s;
void topo()
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    for (int i = 1; i <= n; i++)
        if (!deg[i])
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        s.push_back(u);
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            deg[v]--;
            if (!deg[v])
                q.push(v);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(fir, -1, sizeof(fir));
    s.clear();
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    topo();
    for (int i = s.size() - 1; i >= 0; i--) //倒着做dp
    {
        int u = s[i];
        for (int j = fir[u]; j != -1; j = edge[j].nxt)
        {
            int v = edge[j].v;
            dp[u] = max(dp[u], dp[v] + 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

H - Grid 1

/*
dp[i][j]表示到达(i,j)的方法
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 3;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, m;
char mp[MAXN][MAXN];
int dp[MAXN][MAXN];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    dp[1][1] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; k <= 2; k++)
            {
                int tx = i - (k % 2);
                int ty = j - ((k + 1) % 2);
                if (tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] == '#')
                    continue;
                dp[i][j] += dp[tx][ty];
                dp[i][j] %= mod;
            }
        }
    cout << dp[n][m];
    return 0;
}

I - Coins

/*
dp[i][j]表示前i个硬币,有j个是向上的概率
dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i];
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e3 + 3;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int n, m;
double p[MAXN];
double dp[MAXN][MAXN];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &p[i]);
    dp[1][1] = p[1];
    dp[1][0] = 1.0 - p[1];
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= i; j++)
            if (j)
                dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i];
            else
                dp[i][0] = dp[i - 1][0] * (1 - p[i]);
    double ans = 0.0;
    for (int i = n; i > n / 2; i--)
        ans += dp[n][i];
    printf("%.10f", ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。