首页 > 代码库 > Codeforces 13C Sequence --DP+离散化

Codeforces 13C Sequence --DP+离散化

2024-07-13 20:45:38   222人阅读

题意：给出一个 n (1 <= n <= 5000)个数的序列 。每个操作可以把 n 个数中的某一个加1 或 减 1。问使这个序列变成非递减的操作数最少是多少 

解法：定义dp[i][j]为将前i个数变为以j为结尾的非递减序列的最少操作次数。

则有： dp[i][j] = min(dp[i][j], min(dp[i][k]) + Cost(原来第i个位置上的数转换到j))  (1 <= k <= j)

即前i个数以j结尾的状态可以由前i-1个数以小于等于j的k结尾的状态转移过来，取一个最小的转移

由于输入过大，需要离散化，将数组的复制b[]排序后用到unique函数，unique函数将数组中相邻元素重复的去掉（实际不去掉，只是放到最后面），然后返回最后一个不与其他元相同的数的地址，所以通过unique(b,b+n)-b可得到该数列实际不同的数有多少个，然后我们上述方程中的j就在这些里面取，Cost其实计算方法为abs(b[j]-a[i])

同时数组不可能存下5000*5000，由于每一个状态都从前一个推来，于是可以用滚动数组。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define lll __int64using namespace std;#define N 5007const lll INF = (1LL<<60);lll dp[2][N];lll a[N],b[N];int main(){    int n,i,j;    scanf("%d",&n);    for(i=0;i<n;i++)    {        scanf("%I64d",&a[i]);        b[i] = a[i];    }    sort(b,b+n);    int tot = unique(b,b+n) - b;  //离散化成 0~tot    for(i=0;i<tot;i++)    {        dp[0][i] = abs(b[i]-a[0]);        dp[1][i] = INF;    }    int now = 1;    for(i=1;i<n;i++)    {        lll mini = INF;        for(j=0;j<tot;j++)        {            mini = min(dp[now^1][j],mini);            dp[now][j] = min(dp[now][j],mini+abs(b[j]-a[i]));        }        now = 1-now;        for(j=0;j<tot;j++)            dp[now][j] = INF;    }    lll mini = INF;    for(i=0;i<tot;i++)        mini = min(mini,dp[1-now][i]);    printf("%I64d\n",mini);    return 0;}
View Code


联系
我们