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';
}