[Solution][Dynamic Programming]NOI2006 Worm

首先来看一道非常类似的题目。

吐槽:NOI组委会为何如此偏爱HN,难道真的是虐场无压力么。。。

[HNOI2005]木梳

【题目】

戳这里.

【题意】

给定一些竖直的线段,求最小的总切割长度,使得任意连续三条线段高度不均递增或均递减。
(个人觉得题意转化还是很显然的,却没想出来。。。)

【思路】

根据经验显然是DP.
分析可知最优的决策后,线段必然形成一些整齐的等高块。
我们不妨设表示第i条线段,高度为j,凸凹状态为k时的最小删除代价。
这里,0表示相对于前一个等高块严格下降(凹),1表示相对于前一个等高块严格升高(凸)。
这样我们很容易枚举上一条线段高度和本条线段高度根据其凸凹性列出状态转移方程。过于复杂在此不再阐述。
不过这个方法时间复杂度是的,显然无法通过全部测试数据。
似乎没有更少维度的状态表示。。。看了题解才发现可以贪心。。。不过过于复杂。

可以证明对于线段i,最优目标高度满足

PS:证明百度脑补,我暂时不想知道。
所以我们可以预处理出第i条线段的所有最优决策,转移时只枚举上条线段和本条线段的最优决策。
时间复杂度:,可以通过本题所有数据。

【代码】

/**************************************************************
    Problem: 1200
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:396 ms
    Memory:21120 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
const int N = 100001;
int getint()
{
    int c;
    while((c = getchar())<'0');
    int tmp = c - '0';
    while((c = getchar())>='0')
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
inline void mini(long long &a , long long const &b)
{
    if(a>b)
        a=b;
}
long long dp[N][10][2] ;
int h[N] , st[N][10] , num[N];
int main()
{
    int n;
    scanf("%d" , &n);
    int i , j , k;
    for(i = 1 ; i <= n ; ++i)
        h[i] = getint();
    memset(dp , 0x3f , sizeof(dp));
    for(i = 1 ; i <= n ; ++i)
        for(j = i - 2 ; j <= i + 2 ; ++j)
        {
            if (j < 1 || j > n)
                continue;
            if(h[j]<=h[i])
                st[i][num[i]++] = h[j];
            if(h[j]-1<=h[i])
                st[i][num[i]++] = h[j] - 1;
        }
    for(i = 0 ; i != num[1] ; ++i)
        dp[1][i][0] =dp[1][i][1] =h[1] - st[1][i];
    for(i = 2 ; i <= n ; ++i)
        for(j = 0 ; j != num[i] ; ++j)
        {
            for(k = 0 ; k != num[i - 1] ; ++k)
                if(st[i-1][k]>st[i][j])
                    mini(dp[i][j][0] , dp[i - 1][k][1]);
                else if(st[i-1][k]<st[i][j])
                    mini(dp[i][j][1] , dp[i - 1][k][0]);
                else
                {
                    mini(dp[i][j][0] , dp[i - 1][k][0]);
                    mini(dp[i][j][1] , dp[i - 1][k][1]);
                }
            dp[i][j][0]+=h[i] - st[i][j];
            dp[i][j][1]+=h[i] - st[i][j];
        }
    long long ans = 1LL << 60;
    for(i = 0 ; i != num[n] ; ++i)
        for(j = 0 ; j < 2 ; ++j)
            mini(ans , dp[n][i][j]);
    printf("%lld" , ans);
    return 0;
}

[NOI2006] Worm

在处理了这道题后,Worm这道题就变得非常简单了。
分别在左右两边进行上述算法,求和即可。
(事实上这两道题确实是一个模型。。仔细想想)

【代码】(贝神帮忙优化ORZ)

/**************************************************************
    Problem: 1496
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:312 ms
    Memory:8620 kb
****************************************************************/
 
#include<cstdio>
#include<cctype>
#include<cstring>
#define M(X) (1&(X))
inline void mini(int &a , int const b)
{
    if (a > b)
        a = b;
}
inline int getint()
{
    int c;
    while(!isdigit(c = getchar()));
    int tmp = c - '0';
    while(isdigit(c = getchar()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
const int N = 1000001;
int dpl[2][16][2] ,dpr[2][16][2], l[N] , r[N] , stl[2][16] , numl[2] , str[2][16] , numr[2],n;
void build(int i)
{
    numl[M(i)]=numr[M(i)]=0;
    for(int j = i - 2 ; j <= i + 2 ; ++j)
    {
        if (j < 1 || j > n)
            continue;
        for(int k = 0 ; k <= 2 ; ++k)
        {
            if (l[j] - k <= l[i])
                stl[M(i)][++numl[M(i)]] = l[j] - k;
            if (r[j] + k >= r[i])
                str[M(i)][++numr[M(i)]] = r[j] + k;
        }
    }
}
int main()
{
    scanf("%d" , &n);
    register int i , j , k;
    for(i = 1 ; i <= n ; ++i)
        l[i] = getint() , r[i] = getint();
    build(1);
    memset(dpl[1], 0x3f , sizeof(dpl[1]));
    memset(dpr[1], 0x3f , sizeof(dpr[1]));
    for(i = 1 ; i <= numl[1] ; ++i)
        dpl[1][i][0] = l[1] - stl[1][i];
    for(i = 1 ; i <= numr[1] ; ++i)
        dpr[1][i][0] = str[1][i] - r[1];
    for(i = 2 ; i <= n ; ++i)
    {
        build(i);
        memset(dpl[M(i)], 0x3f , sizeof(dpl[M(M(M(i)))]));
        memset(dpr[M(i)], 0x3f , sizeof(dpr[M(M(M(i)))]));
        for(j = 1 ; j <= numl[M(i)] ; ++j)
        {
            for(k = 1 ; k <= numl[!M(i)]; ++k)
            {
                if (stl[M(i)][j] > stl[!M(i)][k])
                    mini(dpl[M(i)][j][0] , dpl[!M(i)][k][1]);
                else if (stl[M(i)][j] < stl[!M(i)][k])
                    mini(dpl[M(i)][j][1] , dpl[!M(i)][k][0]);
                else
                {
                    mini(dpl[M(i)][j][0] , dpl[!M(i)][k][0]);
                    mini(dpl[M(i)][j][1] , dpl[!M(i)][k][1]);
                }
            }
            dpl[M(i)][j][0] += l[i] - stl[M(i)][j];
            dpl[M(i)][j][1] += l[i] - stl[M(i)][j];
        }
        for(j = 1 ; j <= numr[M(i)] ; ++j)
        {
            for(k = 1 ; k <= numr[!M(i)] ; ++k)
            {
                if (str[M(i)][j] < str[!M(i)][k])
                mini(dpr[M(i)][j][0] , dpr[!M(i)][k][1]);
                else if (str[M(i)][j] > str[!M(i)][k])
                mini(dpr[M(i)][j][1] , dpr[!M(i)][k][0]);
                else
                {
                    mini(dpr[M(i)][j][0] , dpr[!M(i)][k][0]);
                    mini(dpr[M(i)][j][1] , dpr[!M(i)][k][1]);
                }
            }
            dpr[M(i)][j][0] += str[M(i)][j] - r[i];
            dpr[M(i)][j][1] += str[M(i)][j] - r[i];
        }
    }
    int ansl =(1U << 31)-1 ,ansr =(1U << 31)-1;
    for(i = 1 ; i <= numl[M(n)] ; ++i)
        mini(ansl , dpl[M(n)][i][0]);
    for(i = 1 ; i <= numr[M(n)] ; ++i)
        mini(ansr , dpr[M(n)][i][0]);
    printf("%d" , ansl+ansr);
    return 0;
}
comments powered by Disqus