CodeForces - 714E + POJ - 3666 （dp严格单调递增与非严格单调递增）

本是古典何须时尚 2022-05-23 04:20 210阅读 0赞

POJ - 3666 ：

此题是dp非严格单调递增的最小花费，要满足非严格递增，即后一个要大于等于前一个数，现在要求n个数的非严格递增前i个数的花费肯定是前i-1个数花费，再加上第i个数的花费，前i-1个数之能是第i-1个数小于等于第i个数的情况，所以dp转移为：

dp\[i\]\[j\]=abs(a\[i\]-j)+min\{dp\[i-1\]\[k<=j\]\};

就是说你要取i-1个数最后一个数比j小的情况，那这范围大了去了，网上说离散化，意思就是把这些数限制在他给的n个数中。

具体原因也不是很清楚。

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int N=2010;
    int dp[N][N];
    int a[N], b[N];
    
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
             scanf("%d", a+i);
             b[i]=a[i];
        }
    
        sort(a+1, a+1+n);
       
        memset(dp, 0x3f, sizeof(dp));
        memset(dp[0], 0, sizeof(dp[0]));
        for(int i=1; i<=n; i++)
        {
            int mm=INF;
            for(int j=1; j<=n; j++)
            {
                mm=min(mm, dp[i-1][j]);
                dp[i][j]=mm+abs(b[i]-a[j]);
            }
        }
      
        int ans=INF;
        for(int i=1; i<=n; i++)
            ans=min(ans, dp[n][i]);
        printf("%d\n", ans);
    
        return 0;
    }

CodeForces - 714E：

这个题是严格递增，如果非严格递增，那么就要求a\[j\]-a\[i\]>=j-i (j>i),  即a\[j\]-j>=a\[i\]-i, 就是说他给的n个数减去他的下标，求该n个数的非严格递增。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    int n;
    ll a[3010], b[3010];
    ll cos=INF;
    ll dp[3010][3010];
    
    int main(){
        scanf("%d", &n);
    
        for(int i=1; i<=n; i++)
        {
            scanf("%lld", &a[i]);
            a[i]-=i;
            b[i]=a[i];
        }
        sort(b+1, b+1+n);
    
        ll mm;
        memset(dp, 0x3f, sizeof(dp));
        memset(dp[0], 0, sizeof(dp[0]));
        for(int i=1; i<=n; i++){
            mm=INF;
            for(int j=1; j<=n; j++){
                mm=min(dp[i-1][j], mm);
                dp[i][j]=abs(b[j]-a[i])+mm;
            }
        }
        mm=INF;
        for(int i=1; i<=n; i++)
            mm=min(dp[n][i], mm);
        printf("%lld\n", mm);
    
        return 0;
    }