【Kuangbin简单DP】平整数组

旧城等待， 2024-03-30 13:54 55阅读 0赞

[4562. 平整数组 - AcWing题库][4562. _ - AcWing]

题意：

![9e37cc36f3d0449db0725fa908bb4ceb.png][]

思路：

一开始想的是

设DP状态是：dp\[i\]\[0/1\]表示阶段到 i ，然后前面是递增or递减的最小sum的集合

然后我是怎么转移的呢，现在看来感觉挺好笑的：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e3+10;
    int n;
    int a[mxn],dp[mxn][2];
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++){
    		dp[i][0]=dp[i-1][0]+abs(a[i]-a[i-1])*(a[i-1]<a[i]);
    		dp[i][1]=dp[i-1][1]+abs(a[i]-a[i-1])*(a[i-1]>a[i]);
    	}
    	int ans=min(dp[n][0],dp[n][1]);
    	cout<<ans<<'\n';
    }

这尼玛....和贪心有区别嘛....

就是如果满足单调就不去动这个位置的数，否则就把它变成前一个数

这显然不能这样做啊qwq

**状态转移确实是不重不漏了，但是枚举决策和枚举上一层的状态，显然也要满足不重不漏啊**

**要枚举到所有决策和上一层的所有状态，才能保证DP的正确性吧**

我这样写，显然都没枚举决策，直接按照贪心策略去转移了，答案自然是错的

正解应该是这样的：

设dp\[i\]\[j\]表示枚举到阶段 i ，然后第 i 位置选 b\[j\] 的最小sum的集合

其中 b 数组是 a 数组离散化之后的结果，说白了就是 a 数组这个集合

为什么这么设计？首先阶段 i 不用说，**我们去看是什么影响了决策**

是单调性

因此我们要去记录一下该位置放的是什么数

**这也提示了我们，决策是可以放在数组里的**

而且，在状态设计的时候，表示的是**该阶段**的参数，这样好转移

然后怎么转移？

for(int i=1;i<=n;i++){
            for(int j=1;j<=len;j++){
                for(int k=1;k<=j;k++){
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(a[i]-b[j]));
                }
            }
        }

这个咋想到的

转移顺序肯定是满足拓扑序的嘛

即先去枚举阶段 ，再去枚举状态，最后去枚举决策

第一层for循环就是枚举阶段

第二层for循环就是去枚举这个阶段的状态，即位置 i 的状态

然后就是去枚举决策，由于这道题决策也是状态的一部分，所以直接去枚举上一层状态 k

由于要满足单调性，这里先去考虑递增，所以上一层状态一定比这一层小，因此 k 在1到j之间

求完递增的，再求一遍递减的就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10;
    int n,ans=0x3f3f3f3f;
    int a[mxn],b[mxn],dp[mxn][mxn];
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-(b+1);
        memset(dp,0x3f,sizeof(dp));
        for(int j=1;j<=len;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=len;j++){
                for(int k=1;k<=j;k++){
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(a[i]-b[j]));
                }
            }
        }
        for(int j=1;j<=len;j++) ans=min(ans,dp[n][j]);
        memset(dp,0x3f,sizeof(dp));
        for(int j=1;j<=len;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=len;j++){
                for(int k=j;k<=len;k++){
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(a[i]-b[j]));
                }
            }
        }
        for(int j=1;j<=len;j++) ans=min(ans,dp[n][j]);
        cout<<ans<<'\n';
    }

但是这样复杂度是O(n^3)的，太暴力了

我们需要优化一下

**这里复杂度优化的本质是，在枚举这一层阶段的状态时记录上一层状态的最值**

用变量保存一下，然后直接转移就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e3+10;
    int n,ans=1e18;
    int a[mxn],b[mxn],dp[mxn][mxn];
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-(b+1);
        memset(dp,127,sizeof(dp));
        for(int j=1;j<=len;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            int mi=1e18;
            for(int j=1;j<=len;j++){
                mi=min(mi,dp[i-1][j]);
                dp[i][j]=min(dp[i][j],mi+abs(a[i]-b[j]));
            }
        }
        for(int j=1;j<=len;j++) ans=min(ans,dp[n][j]);
        memset(dp,127,sizeof(dp));
        reverse(b+1,b+1+len);
        for(int j=1;j<=len;j++) dp[0][j]=0;
        for(int i=1;i<=n;i++){
            int mi=1e18;
            for(int j=1;j<=len;j++){
                mi=min(mi,dp[i-1][j]);
                dp[i][j]=min(dp[i][j],mi+abs(a[i]-b[j]));
            }
        }
        for(int j=1;j<=len;j++) ans=min(ans,dp[n][j]);
        cout<<ans<<'\n';
    }

[4562. _ - AcWing]: https://www.acwing.com/problem/content/4565/
[9e37cc36f3d0449db0725fa908bb4ceb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e63f2134be3543a982da5e9856771777.png