S - Making the Grade POJ - 3666 结论 将严格递减转化成非严格的

S - Making the Grade

POJ - 3666

这个题目要求把一个给定的序列变成递增或者递减序列的最小代价。

这个是一个dp，对于这个dp的定义我觉得不是很好想，如果第一次碰到的话。

上网看了一下题解，dp[i][j]表示前面 i 位已经是有序的了，第 i+1 位变成第j大的最小代价。

这个转移可以保证有序这个条件。

递增递减d两次。

这个题目要离散化，为什么要离散化呢，推荐博客

我以前就是感觉数据大就要离散化，不然数组存不下，不过看了这篇题解感觉他讲的很对啊。

#include <cstring>

#include <queue>

#include <cstdlib>

#include <cstdio>

#include <iostream>

#include <string>

#include <algorithm>

#include <map>

#include <vector>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 2e3 + ;

ll dp1[maxn][maxn], dp2[maxn][maxn];

int a[maxn], b[maxn];

int main()

{

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];

    sort(b + , b +  + n);

    int len = unique(b + , b +  + n) - b - ;

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= len; j++) {

            dp1[i][j] = dp2[i][j] = inf64;

        }

    }

    for (int i = ; i <= len; i++) {

        dp1[][i] = abs(b[i] - a[]);

        dp2[n][i] = abs(b[i] - a[n]);

    }

    for(int i=;i<n;i++)

    {

        ll tmp = inf64;

        for(int j=;j<=len;j++)

        {

            tmp = min(tmp, dp1[i][j]);//这一步我感觉很巧妙，优化了一个for循环，

            //这里是再找j前面的最小的那个dp[i][j]，因为dp[i][j]=min(dp[i-1][1~j])+abs()

            dp1[i + ][j] = min(dp1[i + ][j], tmp + abs(a[i + ] - b[j]));

        }

    }

    ll ans = inf64;

    for (int i = ; i <= len; i++) ans = min(ans, dp1[n][i]);

    for(int i=n;i>;i--)

    {

        ll tmp = inf64;

        for(int j=;j<=len;j++)

        {

            tmp = min(tmp, dp2[i][j]);

            dp2[i - ][j] = min(dp2[i - ][j], tmp + abs(a[i - ] - b[j]));

        }

    }

    for (int i = ; i <= len; i++) ans = min(ans, dp2[][i]);

    printf("%lld\n", ans);

    return ;

}

然后还有一个题目和这个很类似，好像比这个要难一点，所以我才先写的这个题目。

C. Sonya and Problem Wihtout a Legend

之前的那篇博客也有推荐

这个题目我居然没有写出来，其实和上面基本上是一样的，只有一点点的区别，上面的是非严格的，这个是严格递增的。

然后我不知道怎么转化，或者说我尝试过了，发现不太对。

然后我就去搜了题解，发现有一种方法可以把严格转化成非严格就是 a[i]-i

这样之后求非严格就可以了，然后要注意因为这个是求差值最小，所以这个不会影响答案，

知道这个就很简单了，这个结论以后不要忘记

#include <cstring>

#include <queue>

#include <cstdlib>

#include <cstdio>

#include <iostream>

#include <string>

#include <algorithm>

#include <map>

#include <vector>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 3e3 + ;

ll dp[maxn][maxn];

ll a[maxn], b[maxn];

int main()

{

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        scanf("%lld", &a[i]);

        a[i] -= i;

        b[i] = a[i];

    }

    sort(b + , b +  + n);

    int len = unique(b + , b +  + n) - b - ;

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= len; j++) {

            dp[i][j] = inf64;

        }

    }

    for (int i = ; i <= len; i++) dp[][i] = abs(a[] - b[i]);

    for(int i=;i<n;i++)

    {

        ll tmp = inf64;

        for(int j=;j<=len;j++)

        {

            tmp = min(dp[i][j], tmp);

            dp[i + ][j] = min(dp[i + ][j], tmp + abs(a[i + ] - b[j]));

        }

    }

    ll ans = inf64;

    for (int i = ; i <= len; i++) ans = min(ans, dp[n][i]);

    printf("%lld\n", ans);

    return ;

}