atcoder 官方dp题单题解(持续更新)
题单链接:https://atcoder.jp/contests/dp/tasks
洛谷搜索:https://www.luogu.com.cn/problem/list?keyword=at_dp&type=AT|B|CF|P|SP|UVA&page=1
A
题目链接:https://atcoder.jp/contests/dp/tasks/dp_a
简单线性dp. dp[i]表示在i这个位置的最小代价,转移的时候把两种选择都考虑进去就可以了.
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
vector<int> a(n+1),dp(n+1,0);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
dp[2]=abs(a[1]-a[2]);
for(int i=3;i<=n;i++)
{
dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
}
cout<<dp[n]<<'\n';
}
B
题目链接:https://atcoder.jp/contests/dp/tasks/dp_b
实际上这题数据范围比较小, \(O(nk)\) 的暴力做法也能过去
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
vector<int> a(n+1),dp(n+1,1e9);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
dp[1]=0;
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(a[i]-a[j]));
}
}
cout<<dp[n]<<'\n';
}