AT_dp_a Frog 1
设 \(dp_i\) 表示从 \(1\) 跳到 \(n\) 至少需要多少费用，那么 \(i\) 只能从 \(i-1\) 或 \(i-2\) 跳过来，因此得到
\[dp_i=\min\{dp_{i-1}+|a_i-a_{i-1}|,dp_{i-2}+|a_i-a_{i-2}|\}
\]
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],dp[100005];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
if(i>2)dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
}
cout<<dp[n];
return 0;
}
AT_dp_b Frog 2
看见 \(K\) 非常小，所以可以暴力。
设 \(dp_i\) 表示从 \(1\) 跳到 \(n\) 至少需要多少费用，那么与上题类似
\[dp_i=\min_{j=1}^{min(i-1,k)}dp_{i-j}+|a_i-a_{i-j}|
\]
时间复杂度 \(O(NK)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],dp[100005],k;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++){
dp[i]=LONG_LONG_MAX;
for(int j=1;j<=min(i-1,k);j++)dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i- j]));
}
cout<<dp[n];
return 0;
}
AT_dp_c Vacation
还是很好想的。设 \(dp_{i,j}\) 表示第 \(i\) 天选第 \(j\) 种事情的最大幸福值，那么
\[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
\]
最终答案是 \(\max\{dp_{n,0},dp_{n,1},dp_{n,2}\}\)。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005],b[100005],c[100005],dp[100005][3];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
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];
}
cout<<max({dp[n][0],dp[n][1],dp[n][2]});
return 0;
}
AT_dp_d Knapsack 1
01背包板子。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,W,dp[100005],v[105],w[105],ans;
signed main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)for(int j=W;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for(int i=0;i<=W;i++)ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
AT_dp_e Knapsack 2
注意到 \(\sum{v_i}\le 10^5\)，所以我们可以设 \(dp_i\) 表示选择的物品价值总和是 \(i\) 中的花费最小值，然后类似转移一下就行了，答案也很好求。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,W,w[105],v[105],dp[100005];
signed main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int i=1;i<=n;i++)for(int j=100000;j>=v[i];j--)dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
for(int i=100000;i;i--)if(dp[i]<=W){
cout<<i;
return 0;
}
}
AT_dp_f LCS
求两个字符串的最长公共子序列是很简单的，我们只需要想如何输出最长公共子序列就行了。
实际上可以找到