题解 CF713C 【Sonya and Problem Wihtout a Legend】

IL杰佣 · 2020-07-30 20:50:38 · 题解

重点：数据太水（真的）！

我写这篇题解主要是给那些不懂队列的 OI dalao 们看的，纯dp！！

思路还是讲讲吧。。

首先 把a[ i ]转化成 a[ i ]-1。

dp[ i ][ j ]指的是 i 到 j 的最小代价。从1开始正向跑dp。

so：本题的核心代码是

    minn=min(minn,dp[i-1][j]);
    dp[i][j]=minn+abs(a[i]-read[j]);

前一个最小值加上本次改动的绝对值。

好了，本蒟蒻这次的重点不是讲思路，前面大佬讲过了 ORZ（还有自己不会讲hahaha）

不过我不是光来水题解的，对，开头讲过，纯 dp或加一点点去重,不用队列

No.1:去重优化

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
long long a[3100],read[3100],l,dp[3100][3100],n;
int main()
{
    memset(dp,0x3f3f3f3f,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>read[i];
        read[i]-=i;
        a[i]=read[i];
    }
    sort(read+1,read+n+1);
    l=unique(read+1,read+n+1)-read-1;
    dp[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        long long minn=0x3f3f3f3f3f3f;
        for(int j=1;j<=l;j++)
        {
            minn=min(minn,dp[i-1][j]);
            dp[i][j]=minn+abs(a[i]-read[j]);
        }
    }
    long long minn=0x3f3f3f3f3f3f;
    for(int i=1;i<=;i++)
    {
        minn=min(minn,dp[n][i]);
    }
    cout<<minn;
    return 0;
}

No.2:无优化

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
long long a[3100],read[3100],dp[3100][3100],n;
int main()
{
    memset(dp,0x3f3f3f3f,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>read[i];
        read[i]-=i;
        a[i]=read[i];
    }
    sort(read+1,read+n+1);
    dp[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        long long minn=0x3f3f3f3f3f3f;
        for(int j=1;j<=n;j++)
        {
            minn=min(minn,dp[i-1][j]);
            dp[i][j]=minn+abs(a[i]-read[j]);
        }
    }
    long long minn=0x3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,dp[n][i]);
    }
    cout<<minn;
    return 0;
}

并没有太多区别，不过不去重确实要废一些不必要的时间