POJ 3666 Making the Grade

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://vjudge.net/problem/POJ-3666

题目翻译

有N个数的序列，修改其中的一些数字，使得序列单调不下降。修改的代价极为|X before – X after|

题解

我们把高度离散化，然后F[i][j]表示第i个数字，变成j，使1~i都合法的最小代价。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int Maxn = 2000;
const LL Inf = 2e12;
int n;
LL num[Maxn + 5];
LL rnum[Maxn + 5];
LL rev[Maxn + 5];
struct HashNode
{
    int height;
    int index;
};
HashNode hn[Maxn + 5];
int tot;
LL DP[2][Maxn + 5];
inline LL absX(LL x){
    if (x < 0) return -x;
    return x;
}
inline bool cmpHashNode(HashNode a, HashNode b)
{
    return a.height < b.height;
}
inline LL solveProblem(LL num[], int n, LL height[], int maxH){
    //printf("SolveProblem\n");
    memset(DP, 0, sizeof(DP));
    for (int h = 1; h <= maxH; h++)
        DP[1][h] = absX(height[num[1]] - height[h]);
    for (int si = 2; si <= n; si++)
    {
        int i = si & 1;
        int ni = i ^ 1;
        //for (int h = 1; h <= maxH; h++) if (DP[ni][h] <= Inf) printf("DP[%d][%lld] = %lld\n", si-1, height[h], DP[ni][h]);
        LL ratMin = Inf;
        for (int h = 1; h <= maxH; h++)
        {
            ratMin = min(DP[ni][h], ratMin);
            DP[i][h] = ratMin + absX(height[h] - height[num[si]]);
        }
    }
    //for (int h = 1; h <= maxH; h++) if (DP[n&1][h] <= Inf) printf("DP[%d][%lld] = %lld\n", n, height[h], DP[n&1][h]);
    LL ret = Inf;
    for (int i = 1; i <= maxH; i++)
        ret = min(ret, DP[n&1][i]);
    //printf("Ans : %lld\n", ret);
    return ret;
}
inline void solve()
{
    for (int i = 1; i <= n; i++)
        scanf("%d", &num[i]);
    for (int i = 1; i <= n; i++)
    {
        hn[i].height = num[i];
        hn[i].index = i;
    }
    sort(hn + 1, hn + n + 1, cmpHashNode);
    tot = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i == 1 || hn[i].height != hn[i-1].height){
            tot++;
            rev[tot] = hn[i].height;
        }
        num[hn[i].index] = tot;
    }
    rev[0] = -1;
    for (int i = 1; i <= n; i++) rnum[i] = num[n - i + 1];
    num[0] = rnum[0] = 0;
    LL Ans = min(solveProblem(num, n, rev, tot), solveProblem(rnum, n, rev, tot));
    printf("%lld\n", Ans);
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) != EOF)
        solve();
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int Maxn = 2000;

const LL Inf = 2e12;

int n;

LL num[Maxn + 5];

LL rnum[Maxn + 5];

LL rev[Maxn + 5];

struct HashNode

{

int height;

int index;

};

HashNode hn[Maxn + 5];

int tot;

LL DP[2][Maxn + 5];

inline LL absX(LL x){

if (x < 0) return -x;

return x;

}

inline bool cmpHashNode(HashNode a, HashNode b)

{

return a.height < b.height;

}

inline LL solveProblem(LL num[], int n, LL height[], int maxH){

//printf("SolveProblem\n");

memset(DP, 0, sizeof(DP));

for (int h = 1; h <= maxH; h++)

DP[1][h] = absX(height[num[1]] - height[h]);

for (int si = 2; si <= n; si++)

{

int i = si & 1;

int ni = i ^ 1;

//for (int h = 1; h <= maxH; h++) if (DP[ni][h] <= Inf) printf("DP[%d][%lld] = %lld\n", si-1, height[h], DP[ni][h]);

LL ratMin = Inf;

for (int h = 1; h <= maxH; h++)

{

ratMin = min(DP[ni][h], ratMin);

DP[i][h] = ratMin + absX(height[h] - height[num[si]]);

}

//for (int h = 1; h <= maxH; h++) if (DP[n&1][h] <= Inf) printf("DP[%d][%lld] = %lld\n", n, height[h], DP[n&1][h]);

LL ret = Inf;

for (int i = 1; i <= maxH; i++)

ret = min(ret, DP[n&1][i]);

//printf("Ans : %lld\n", ret);

return ret;

}

inline void solve()

{

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

scanf("%d", &num[i]);

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

{

hn[i].height = num[i];

hn[i].index = i;

}

sort(hn + 1, hn + n + 1, cmpHashNode);

tot = 0;

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

{

if (i == 1 || hn[i].height != hn[i-1].height){

tot++;

rev[tot] = hn[i].height;

}

num[hn[i].index] = tot;

}

rev[0] = -1;

for (int i = 1; i <= n; i++) rnum[i] = num[n - i + 1];

num[0] = rnum[0] = 0;

LL Ans = min(solveProblem(num, n, rev, tot), solveProblem(rnum, n, rev, tot));

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

}

int main()

{

//freopen("in.txt", "r", stdin);

while(scanf("%d", &n) != EOF)

solve();

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑