AtCoder DP Contest 题目全讲（上）

前言：

洛谷题单（非本人整理）

有一些好写的题就不贴代码了，细节较多的再放上。

本篇文章为上期（收录题目 $\text{A–>N}$），题目较为基础，进阶题目放在下期讲解 （目前还在咕咕咕） 。

---

A题

非常简单的方程。
f i = min ⁡ { f i − 1 + ∣ h i − h i − 1 ∣ , f i − 2 + ∣ h i − h i − 2 ∣ } f_i=\min \{f_{i-1}+|h_i-h_{i-1}|,f_{i-2}+|h_i-h_{i-2}|\} fi​=min{fi−1​+∣hi​−hi−1​∣,fi−2​+∣hi​−hi−2​∣}，递推一下就行了。

B题

跟上一题方程几乎一样，只需要枚举一下 $k$ 即可，时间复杂度 $O(nk)$。

C题

很简单的题，设 $f_{i,j}$ 表示第 $i$ 天做第 $j$ 种活动能得到的最大幸福度，答案为 max ⁡ j = 1 3 { f n , j } \max_{j=1}^{3}\{f_{n,j}\} maxj=13​{fn,j​}。

初始化和转移很简单，就不说了。

D题

$01$ 背包问题模版，不再细说。

E题

数据范围变了一下，体积很大，价值很小。我们的思维也跟着一起变，从价值入手，设 $f_i$ 表示得到 $i$ 价值的物品所需的最小重量，转移与 $01$ 背包一样。

最后扫一遍 $f$ 数组，若 $f_i\le W$，就可以更新最大值。

F题

求最长公共子序列，要求输出这个序列。

输出 $\text{dp}$ 方案的套路就是记录该状态从哪转移过来，对于这道题也一样，记录 $f_{i,j}$ 是由 $f_{i-1,j},f_{i,j-1},f_{i-1,j-1}$ 的哪一种转移来，然后倒序输出即可。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
const int N=3010;
int n,m,f[N][N],x[N][N],y[N][N];
char a[N],b[N];
void print(int i,int j){
	if(!i||!j) return;
	print(i-x[i][j],j-y[i][j]);
	if(a[i]==b[j]) cout<<a[i];
}
int main(){
	cin>>(a+1)>>(b+1);
	n=strlen(a+1),m=strlen(b+1);
	FOR(i,1,n){
		FOR(j,1,m){
			if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1,x[i][j]=1,y[i][j]=1;
			else if(f[i-1][j]>f[i][j-1]) f[i][j]=f[i-1][j],x[i][j]=1;
			else f[i][j]=f[i][j-1],y[i][j]=1;
		}
	}
	print(n,m);
	return 0;
}

G题

经典拓扑排序 + $\text{dp}$。因为是 $\text{DAG}$，所以先拓扑排序求出序列，然后按顺序枚举所有点进行更新。

设 $f_i$ 表示走到 $i$ 点的最长路，答案为 max ⁡ i = 1 n { f i } \max_{i=1}^{n}\{f_i\} maxi=1n​{fi​}。

对于边 $(x,y)$，更新为 f y = max ⁡ { f x + 1 } f_y=\max\{f_x+1\} fy​=max{fx​+1}，这道题就做完了。

H题

$O(n^2)$ 暴力递推即可，注意判断边界条件和是否可行。

这道题的加强版是很有意思的，是 Y 题，有能力的可以先行去看它。

I题

比较简单的概率题。

设 $f_{i,j}$ 表示前 $i$ 枚硬币，有 $j$ 枚朝上，初始化 $f_{1,1}=p_1,f_{1,0}=1-p_1$。
转移是显然的，$f_{i,j}=f_{i-1,j}\times (1-p_i)+f_{i-1,j-1}\times p_i$，注意 $j=0$ 的情况。
最后统计答案为 ${\sum }_{i=\lfloor \frac{n}{2}\rfloor +1}^n$