AtCoder DP Contest 题目全讲（上）

非常简单的方程。
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​∣}，递推一下就行了。

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

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

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

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

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

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

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

输出 $\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;
}

经典拓扑排序 + $\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}，这道题就做完了。

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

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

比较简单的概率题。

设 $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{f}_{n,i}$。

期望题，难度薄纱了 $\text{I}$ 题。

我们发现只需关心每个 $a$ 值出现的次数，而不关心盘子的具体信息，所以从此角度出发设计状态。

设 $f_{i,j,k}$ 表示 $1$ 有 $i$ 个，$2$ 有 $j$ 个，$3$ 有 $k$ 个，$0$ 显然有 $n-i-j-k$ 个，考虑转移：

• 随机到 $0$，答案为 $\frac{n-i-j-k}{n}\times (f_{i,j,k}+1)$。
• 随机到 $1$，答案为 $\frac{i}{n}\times (f_{i-1,j,k}+1)$。
• 随机到 $2$，答案为 $\frac{j}{n}\times (f_{i+1,j-1,k}+1)$。
• 随机到 $3$，答案为 $\frac{k}{n}\times (f_{i,j+1,k-1}+1)$。

将所有式子加起来并进行化简，得到 $f_{i,j,k}=\frac{i{f}_{i-1,j,k}+j{f}_{i+1,j-1,k}+k{f}_{i,j+1,k-1}+n}{i+j+k}$。

枚举 $i,j,k$ 转移即可，注意按 $k,j,i$ 的顺序枚举，防止后效性。

时间复杂度 $O(n^3)$。

#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=310;
int n,a[N];double f[N][N][N];
int main(){n=rd;FOR(i,1,n){int x=rd;a[x]++;}FOR(k,0,n) FOR(j,0,n) FOR(i,0,n){if(!i&&!j&&!k) continue;f[i][j][k]=n;if(i) f[i][j][k]+=i*f[i-1][j][k];if(j) f[i][j][k]+=j*f[i+1][j-1][k];if(k) f[i][j][k]+=k*f[i][j+1][k-1];f[i][j][k]/=i+j+k;}printf("%.12lf\n",f[a[1]][a[2]][a[3]]);return 0;
}

博弈论，但本质还是 $\text{dp}$ 求解。

不难发现以下结论：

• 只剩 $0$ 颗石子时，当前操作者必败。
• 每个人会选择最佳策略，所以只要当前状态能到达必败态，那么这个人就获胜了。

所以 $f_0=0$，然后我们枚举石子，枚举所选集合，递推就可以了。

又是博弈，思考策略。

发现经过某些轮后，最后剩下的一定是一段连续区间，再看数据范围，似乎允许区间 $\text{dp}$。所以我们设 $f_{i,j}$ 表示剩下区间 $[i,j]$ 时先手能得到的最大分数差。

转移时考虑两个人的博弈过程：

• 若取走了偶数个数，此时先手取，$f_{i,j}=\max (f_{i+1,j}+a_i,f_{i,j-1}+a_j)$。
• 若取走了奇数个数，此时后手取，$f_{i,j}=\min (f_{i+1,j}-a_i,f_{i,j-1}-a_j)$。

时间复杂度 $O(n^2)$。

求方案数，状态设计和转移非常显然：设 $f_{i,j}$ 表示前 $i$ 个人，总共分了 $j$ 个糖果的方案数，答案 $f_{n,k}$。

转移时枚举 $i$ 选了多少糖果： $f_{i,j}={\sum }_{k=0}^{a_i}{f}_{i-1,j-k}$，时间复杂度 $O(n{k}^2)$，考虑优化。

发现转移的是一个区间 $[max(0,j-a_i),j]$，可以使用前缀和优化，注意处理数组越界情况（虽然好像越界也能过 ），然后就做完了。

#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=110,M=1e5+10,mod=1e9+7;
int n,k,f[N][M],s[N][M],a[N];
int main(){n=rd,k=rd;FOR(i,1,n) a[i]=rd;FOR(i,0,a[1]) f[1][i]=1;s[1][0]=f[1][0];FOR(i,1,k) s[1][i]=s[1][i-1]+f[1][i];FOR(i,2,n){FOR(j,0,k){if(j-a[i]<=0) f[i][j]=s[i-1][j];else f[i][j]=(1ll*s[i-1][j]-s[i-1][j-a[i]-1]+mod)%mod;if(j>0) s[i][j]=(s[i][j-1]+f[i][j])%mod;else s[i][j]=f[i][j];}}printf("%d\n",f[n][k]);return 0;
}

经典区间 $\text{dp}$，设 $f_{i,j}$ 表示将区间 $[i,j]$ 合并为一段的最小花费，答案 $f_{1,n}$，转移时枚举区间断点 $k$，则
f i , j = min ⁡ { f i , k + f k + 1 , j + sum ( i , j ) } f_{i,j}=\min\{f_{i,k}+f_{k+1,j}+\text{sum}(i,j)\} fi,j​=min{fi,k​+fk+1,j​+sum(i,j)}。