前言-为什么要写这个笔记
其实是因为今天写了 AtCoder DP Contest（以下简称
AT_dp）的前三道简单DP题，然后就想做个笔记存档一下，不然以后再想找回这个专题的代码不太方便。另一方面，也算是为我的DP复习学习之路开启一页新的篇章（算是系统化的重修了）。当然，这个笔记也不限于AtC的题目，洛谷等OJ上的题目也会被包含在内。笔记的范围大致是从今天开始写的DP题（再加上暑假时写过的几道题），预计可能一直更新三四年甚至更久。嗯，即使可能不去打XCPC，我还是会继续学点算法的。
AtCoder DP Contest
AtCoder DP
Contest（洛谷题单）
正文
20241023
AT_dp_a Frog_1
这题确实很简单。
1
2
3
4
5
6
7
8
9
10
11
12
| using namespace std;
int h[100005],dp[100005];
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>h[i];
dp[2]=abs(h[2]-h[1]);
for(int i=3;i<=n;++i) dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
cout<<dp[n];
return 0;
}
|
AT_dp_b Frog_2
这题也还好，就是注意别越界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
constexpr int MAX=1e9;
int h[100005],dp[100005];
int main(){
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i) cin>>h[i];
for(int i=2;i<=n;++i) dp[i]=MAX;
for(int i=2;i<=n;++i){
for(int j=max(1,i-k);j<i;++j){
dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
}
}
cout<<dp[n];
return 0;
}
|
AT_dp_c Vacation
洛谷中文翻译
他不能连续两天以上做同样的活动中的两天以上其实是包含两天的（原题面的日文好像也没强调）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
int dp[3][(int)1e5+3];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>dp[0][i]>>dp[1][i]>>dp[2][i];
if(i==1) continue;
dp[0][i]+=max(dp[1][i-1],dp[2][i-1]);
dp[1][i]+=max(dp[0][i-1],dp[2][i-1]);
dp[2][i]+=max(dp[0][i-1],dp[1][i-1]);
}
cout<<max({dp[0][n],dp[1][n],dp[2][n]});
return 0;
}
|