当前位置：首页 > article >正文

动态规划（DP）（细致讲解+例题分析）

article 2025/1/23 10:05:24

动态规划（DP）

本章将介绍介绍动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化。

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

动态规划原理

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

最优子结构

具有最优子结构也可能是适合用贪心的方法求解。

注意要确保我们考察了最优解中用到的所有子问题。

证明问题最优解的第一个组成部分是做出一个选择；
对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

原问题的最优解中涉及多少个子问题；
确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

无后效性

已经求解的子问题，不会再受到后续决策的影响。

子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；
寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
按顺序求解每一个阶段的问题。

如果用图论的思想理解，我们建立一个有向无环图，每个状态对应图上一个节点，决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长（短）路的问题（参见：DAG 上的 DP）。

[P1048 NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态

首先定义状态 $d p [i] [j]$ 以 j 为容量为放入前i个物品(按 ii 从小到大的顺序)的最大价值，那么 i=1 的时候，放入的是物品 1 ，这时候肯定是最优的啦！

那考虑一下 j，j是当前容量，如果 j<5，那么是不是就不能放， $d p [1] [j] (j < 5) = 0$ ；那如果 j>5，就可以放了， $d p [1] [j] (j >= 5) = 20$ ；

接着 i=2 放两个物品，求的就是 $d p [2] [j]$ 了，当 j<5 的时候，是不是同样的 $d p [2] [j] (j < 5)$ 等于0；那当 j<6 是不是还是放不下第二个，只能放第一个；

那 j>6 呢？是不是就可以放第二个了呢？是可以，但是明显不是最优的，用脑子想了一下，发现 $d p [2] [j] (j > 6) = 20$ ，这个 20 怎么来的呢，当然是从前一个状态来的（注意这里就可以分为两种情况了）：一种是选择第二个物品放入，另一种还是选择前面的物品；

让我们假设一下 j=10吧，可能会比较好理解！这时候：

$d p [2] [10] = ma x ((d p [1] [10 - w [2]]) + v [2], d p [1] [10])$

$d p [2] [10] = ma x (d p [1] [4]) + 10, d p [1] [10])$

#include<set>
#include<fstream>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<bitset>
#define endl '\n'
using namespace std;
using ll = long long;
int dp[1001][1010];
int main()
{
	vector<int>v1(1001);
	vector<int>v2(1001);
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> v1[i] >> v2[i];
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (v1[i] <= j)
			{
				dp[i][j] = max(dp[i - 1][j], v2[i] + dp[i - 1][j - v1[i]]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[n][m];


	return 0;
}

#include<map>
#include<set>
#include<fstream>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<bitset>
#define endl '\n'
#define int long long
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define init ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using ll = long long;

int n, m;
vector<int>v1(1005, 0);

signed main()
{
	init;

	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b; cin >> a >> b;
		for (int j = n; j > 0; --j)
		{
			if (v1[j] > 0 && (j + a) <= n && (v1[j] + b) > v1[j + a])
			{
				v1[j + a] = v1[j] + b;
			}
		}
		if (a <= n && b > v1[a])
		{
			v1[a] = b;
		}
	}
	int max = 0;
	for (int i = n; i >= 1; --i)
	{
		if (v1[i] > max)
		{
			max = v1[i];
		}
	}
	cout << max;
	return 0;
}

P1510 精卫填海 - 洛谷 | 计算机科学教育新生态

然后就该开始无尽的思索了这题的状态转移方程是什么？

本蒟蒻的思路是将体力看做背包将石子看做物品然后就很自然地得出了本题的状态转移方程：

f[j]=max(f[j],f[j-w[i]]+v[i])

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> f, w, v;

int main() {  
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int vn, n, c, sum = 0;
    cin >> vn >> n >> c;
    v.resize(n + 1);
    w.resize(n + 1);
    f.resize(c + 1, 0);

    for(int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
        sum += v[i];
    }

    if(sum < vn) {
        cout << "Impossible" << '\n';
        return 0;
    }

    for(int i = 1; i <= n; ++i)
        for(int j = c; j >= w[i]; --j) f[j] = max(f[j], f[j - w[i]] + v[i]);

    for(int i = 0; i <= c; ++i) {
        if(f[i] >= vn) {
            cout << c - i << '\n';
            return 0;
        }
    }

    cout << "Impossible" << '\n';
}

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;

int v, n, c;
int weight[N];

void solved()
{
    cin >> v >> n >> c;

    for (int i = 0; i < n; ++i)
    {
        int k, m;
        cin >> k >> m;
        for (int j = c; j >= m; --j)
        {
            weight[j] = max(weight[j - m] + k, weight[j]);
        }
    }

    for (int i = 0; i <= c; ++i)
    {
        if (weight[i] >= v)
        {
            cout << c - i;
            return;
        }
    }
    cout << "Impossible";
}

signed main()
{
    BoBoowen;

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solved();
    }
}

P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;

int dp[10000010];

void solved()
{
    int t, m;
    cin >> t >> m;

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        for (int j = 0; j <= t; ++j)
        {
            if (j + a > t)
            {
                break;
            }
            dp[j + a] = max(dp[j + a], dp[j] + b);
        }
    }

    int ans = 0;
    for (int i = 0; i <= t; ++i)
    {
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

signed main()
{
    BoBoowen;

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solved();
    }
}

P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态

我们其实不难看出，对于n2n2做法而言，其实就是暴力枚举：将每个状态都分别比较一遍。但其实有些没有必要的状态的枚举，导致浪费许多时间，当元素个数到了104−105104−105以上时，就已经超时了。而此时，我们可以通过另一种动态规划的方式来降低时间复杂度：

将原来的dp数组的存储由数值换成该序列中，上升子序列长度为i的上升子序列，的最小末尾数值

这其实就是一种几近贪心的思想：我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到这条我们臆测的、可作为结果、的上升子序列中。

#include<map>
#include<set>
#include<fstream>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<bitset>
#define endl '\n'
using namespace std;
using ll = long long;

/*
vector<int>v1, v2;
map<int, int>mp1;
int dp1[100005], dp2[100005];

signed main()
{
	int n;
	cin >> n;
	int s2 = 1;
	for (int i = 0; i < n; ++i)
	{
		int x; cin >> x;
		mp1[x] = i;
	}
	
	for (int i = 0; i < n; ++i)
	{
		int x; cin >> x;
		if (x > dp2[s2 - 1] && mp1[x] > mp1[dp2[s2 - 1]])
		{
			dp2[s2] = x;
			s2++;
			continue;
		}
		for (int j = s2 - 1; j > 0; --j)
		{
			if (dp2[j + 1] > x && dp2[j] < x && mp1[x] > mp1[dp2[j]] && mp1[x] < mp1[dp2[j + 1]])
			{
				dp2[j] = x;
				break;
			}
		}
	}
//	for (int i = 0; i <= n; ++i)cout << dp2[i];

	for (int i = n; i >= 0; --i)
	{
		if (0 != dp2[i])
		{
			cout << i;
			break;
		}
	}

	return 0;
}
*/

int N = 0x7fffffff;
int a[100001], b[100001], mapn[100001], f[100001], len;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		mapn[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i)
	{
		cin >> b[i];
		f[i] = N;
	}
	for (int i = 1; i <= n; i++)
	{
		int l = 0, r = len, mid;
		if (mapn[b[i]] > f[len])
		{
			f[++len] = mapn[b[i]];
			
		}
		else
		{
			while (l < r)
			{
				mid = (l + r) / 2;
				if (f[mid] > mapn[b[i]])r = mid;
				else l = mid + 1;
			}
			f[l] = min(mapn[b[i]], f[l]);
		}
	}
	cout << len << '\n';

}

[P1002 NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;

int fx[10] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int fy[10] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int p[30][30];
int dp[30][30];

void solved()
{
    int x, y;
    int mx, my;
    cin >> x >> y >> mx >> my;
    x += 2;
    y += 2;
    mx += 2;
    my += 2;
    for (int i = 0; i < 9; ++i)
    {
        p[mx + fx[i]][my + fy[i]] = 1;
    }

    if (p[2][3] == 0)
    {
        dp[2][3] = 1;
    }
    if (p[3][2] == 0)
    {
        dp[3][2] = 1;
    }

    for (int i = 2; i <= x; ++i)
    {
        for (int j = 2; j <= y; ++j)
        {
            if (p[i][j] == 1)
            {
                continue;
            }
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
        }
    }

    // for (int i = 2; i <= x; ++i)
    // {
    //     for (int j = 2; j <= y; ++j)
    //     {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    cout << dp[x][y];
}

signed main()
{
    BoBoowen;

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solved();
    }
}

D - AtCoder Janken 3

定义 $\operatorname{dp} _ i[H]\ (H\in\lbrace$ R、P、S $\rbrace)$ by：

$\operatorname{dp} _ i[H]\coloneqq$ 在高桥的符合条件的前 $i$ 手牌中，高桥赢的最大手数，这样他的 $i$ /手牌是 $H$ 。

为了方便起见，我们在这里定义 $\operatorname{dp} _ 0[H]=0$ 。(DP代表动态编程）。

高桥的 $i$ 步棋完全取决于青木的 $i$ 手和高桥的 $i$ 手。

因此， $\operatorname{dp} _ i[H]\ (H\in\lbrace$ R, P, S $\rbrace)$ 可以根据 $\operatorname{dp} _ {i-1}\ (H\in\lbrace$ R, P, S $\rbrace)$ （和值 $S _ i$ ）求出。

具体来说，如果 $a$ 赢得 $b$ ，则 $\operatorname{rps}(a,b)$ 为 $1$ ；如果 $a$ 输了，则 $- 1$ 为 $b$ ；如果它们平局，则 $0$ 为 $\operatorname{rps}(a,b)$ （这里的rps代表剪刀石头布），那么

$\operatorname{dp} _ i[H]=\begin{cases}\displaystyle\max _ {H^\prime\neq H}\operatorname{dp} _ {i-1}[H^\prime]&\ &(\operatorname{janken}(H,S _ i)=0)\\1+\displaystyle\max _ {H^\prime\neq H}\operatorname{dp} _ {i-1}[H^\prime]&&(\operatorname{janken}(H,S _ i)=1)\\0&&(\operatorname{janken}(H,S _ i)=-1).\end{cases}$

虽然我们可以在输时将 $-\infty$ 设为DP表中的值，但我们可以证明设置 $0$ 仍然可以得到一个正确的值。

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define answer ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int N = 2 * 1e5;
int dp[N + 1][4];

signed main()
{
	answer;

	int n;
	cin >> n;
	string s;
	cin >> s;
	s = ' ' + s;
	for (int i = 1; i <= n; ++i)
	{
		if (s[i] == 'R')
		{
			dp[i][2] = max({dp[i - 1][1], dp[i - 1][3]}) + 1;
			dp[i][1] = max({dp[i - 1][2], dp[i - 1][3]});
			dp[i][3] = 0;
		}
		if (s[i] == 'P')
		{
			dp[i][3] = max({dp[i - 1][1], dp[i - 1][2]}) + 1;
			dp[i][2] = max({dp[i - 1][1], dp[i - 1][3]});
			dp[i][1] = 0;
		}
		if (s[i] == 'S')
		{
			dp[i][1] = max({dp[i - 1][2], dp[i - 1][3]}) + 1;
			dp[i][3] = max({dp[i - 1][1], dp[i - 1][2]});
			dp[i][2] = 0;
		}
		// cout << max({dp[i][1], dp[i][2], dp[i][3]});
	}
	cout << max({dp[n][1], dp[n][2], dp[n][3]});
	return 0;
}

Problem - 7405

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;

int f[N];
int a[N];
int n, m;

void solved()
{
    memset(f, 0, sizeof f);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        int s;
        cin >> s;
        a[i] = s;
    }
    sort(a + 1, a + n + 1);
    if (a[n] == m)
    {
        cout << "0" << endl;
        return;
    }
    int ans = inf;
    for (int i = 1; i <= n; ++i)
    {
        if (f[m - a[i]])
        {
            ans = min(ans, a[i] - f[m - a[i]]);
        }
        for (int j = m; j >= a[i]; j--)
        {
            f[j] = max(f[j], f[j - a[i]]);
        }
        f[a[i]] = a[i];
    }
    if (ans == inf)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << ans << endl;
    }
}

signed main()
{
    BoBoowen;

    int T = 1;
    cin >> T;
    while (T--)
    {
        solved();
    }
}

Problem - 2050E - Codeforces

让我们运用动态编程的思想。将字符串 $a$ 作为长度为 $i$ 的前缀，字符串 $b$ 作为长度为 $j$ 的前缀，字符串 $c$ 作为长度为 $i + j$ 的前缀，设 $d p [i] [j]$ 为问题答案。

这样，动态编程递归就很容易了：我们需要遍历字符串 $c$ 的下一个（( $i + j$ ）-th）字符的位置。

如果该字符取自字符串 $a$ ，则答案为

$d p [i - 1] [j]$ ，如果是 $a_i = c_{i+j}$ 、
否则为 $d p [i - 1] [j] + 1$ （因为我们需要用 $c_{i+j}$ 替换字符 $a_i$ ）。

如果取自字符串 $b$ ，答案的计算方法与此类似：

$d p [i] [j - 1]$ ，如果是 $b_j = c_{i+j}$ 、
否则为 $d p [i] [j - 1] + 1$ 。

因此，要获得当前动态编程状态的最小值，我们需要取两个所得值的最小值。

为了得到答案，我们需要取动态编程表中位于 $d p [n] [m]$ 处的值，其中 $n$ 是字符串 $a$ 的长度，而 $m$ 是字符串 $b$ 的长度。

每个测试用例的最终时间复杂度为 $\mathcal{O}(n \cdot m)$ 。

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 4e3 + 10;

int n1, n2, n3;
string s1, s2, ss;
int dp[M][M];

void solved()
{
    cin >> s1 >> s2 >> ss;
    n1 = s1.size();
    n2 = s2.size();
    n3 = ss.size();
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    ss = ' ' + ss;

    for (int i = 0; i <= n1; ++i)
    {
        for (int j = 0; j <= n2; ++j)
        {
            dp[i][j] = inf;
        }
    }

    dp[0][0] = 0;
    for (int i = 1; i <= n1; ++i)
    {
        if (s1[i] == ss[i])
        {
            dp[i][0] = dp[i - 1][0];
        }
        else
        {
            dp[i][0] = dp[i - 1][0] + 1;
        }
    }

    for (int j = 1; j <= n2; ++j)
    {
        if (s2[j] == ss[j])
        {
            dp[0][j] = dp[0][j - 1];
        }
        else
        {
            dp[0][j] = dp[0][j - 1] + 1;
        }
    }

    for (int i = 1; i <= n1; ++i)
    {
        for (int j = 1; j <= n2; ++j)
        {
            if (s1[i] == ss[i + j])
            {
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            }
            else
            {
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            }

            if (s2[j] == ss[i + j])
            {
                dp[i][j] = min(dp[i][j], dp[i][j - 1]);
            }
            else
            {
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
            }
        }
    }

    cout << dp[n1][n2] << endl;
}

signed main()
{
    BoBoowen;

    int T = 1;
    cin >> T;
    while (T--)
    {
        solved();
    }
}

Problem - 1096D - Codeforces

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;

int dp[N];

void solved()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(s.size());
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'h')
        {
            dp[0] += a[i];
        }
        else if (s[i] == 'a')
        {
            dp[1] = min(dp[0], dp[1] + a[i]);
        }
        else if (s[i] == 'r')
        {
            dp[2] = min(dp[1], dp[2] + a[i]);
        }
        else if (s[i] == 'd')
        {
            dp[3] = min(dp[2], dp[3] + a[i]);
        }
    }
    cout << dp[3] << endl;
}

signed main()
{
    BoBoowen;

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solved();
    }
}

Problem - G - Codeforces

#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=10005;
int n,W,k,suf[N],f[N],ans; pi p[N];
signed main()
{
	RI i,j; for (scanf("%lld%lld%lld",&n,&W,&k),i=1;i<=n;++i)
	scanf("%lld%lld",&p[i].fi,&p[i].se); sort(p+1,p+n+1);
	priority_queue <int,vector <int>,greater <int>> hp;
	for (i=n;i>=n-k+1;--i) suf[i]=suf[i+1]+p[i].se,hp.push(p[i].se);
	for (i=n-k;i>=1;--i) hp.push(p[i].se),suf[i]=suf[i+1]+p[i].se-hp.top(),hp.pop();
	for (ans=suf[1],i=1;i<=n;++i)
	{
		for (j=W;j>=p[i].fi;--j) f[j]=max(f[j],f[j-p[i].fi]+p[i].se);
		for (j=0;j<=W;++j) ans=max(ans,f[j]+suf[i+1]);
	}
	return printf("%lld",ans),0;
}

查看全文

http://www.kler.cn/a/514747.html