[BZOJ1496/Luogu2703][NOI2006]千年虫(动态规划)

发布于 2018-04-10  115 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1496/Luogu2703][NOI2006]千年虫(动态规划)

Description

千年虫是远古时代的生物,时隔几千万年,千年虫早已从地球上销声匿迹,人们对其知之甚少。考古生物学家最近开始对其有了兴趣,因为一批珍贵的千年虫化石被发现,这些化石保留了千年虫近乎完整的形态。理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型,并且据此判定出千年虫就是蜈蚣的祖先!但科学家J发现了实际与理论的一些出入,他仔细的研究了上百个千年虫化石,发现其中大部分千年虫的形态都不完全符合理论模型,这到底是什么因素造成的呢?理论科学家K敏锐的指出,千年虫的形态保存在化石中很有可能发生各种变化,即便最细微的变化也能导致它不符合模型。于是,摆在科学家面前的新问题诞生了:判断一个化石中的千年虫与理论模型的差距有多大?具体来说,就是根据一个千年虫化石的形态A,找到一个符合理论模型的形态B,使得B是最有可能在形成化石时变成形态A。
BZOJ1496-1
理论学家提出的“千年虫形态特征模型”如下(如上图所示):躯体由头、尾、躯干、足四大部分构成。1.头,尾用一对平行线段表示。称平行于头、尾的方向为x方向;垂直于x的方向为y方向;2.在头尾之间有两条互不相交的折线段相连,他们与头、尾两条线段一起围成的区域称为躯干,两条折线段都满足以下条件:拐角均为钝角或者平角,且包含奇数条线段,从上往下数的奇数条垂直于x方向。3.每条折线段从上往下数的第偶数条线段的躯干的另一侧长出一条足,即一个上、下底平行于x方向的梯形或矩形,且其中远离躯干一侧的边垂直于x方向。注意:足不能退化成三角形(即底边的长度均大于零),躯干两侧足的数目可以不一样。(如下图,左边有4条足,右边有5条足)
BZOJ1496-2
可见,x-y直角坐标系内,躯干和所有足组成的实心区域的边界均平行或垂直于坐标轴。为了方便,我们假设所有这些边界的长度均为正整数。因此可以认为每个千年虫的躯体都由一些单位方格拼成。每个单位方格都由坐标(x,y)唯一确定。设头尾之间的距离为n,则我们可以用2×n个整数来描述一条千年虫B(如右图):将B沿平行x轴方向剖分成n条宽度为1的横条,每个横条最左边一格的x坐标设为Li,最右一格的的x坐标设为Ri。则(n,L1,L2,..,Ln,R1,R2,..Rn)就确定了一条千年虫。 由于岁月的侵蚀,在实际发现的化石中,千年虫的形状并不满足上面理论模型的规则,一些格子中的躯体已经被某些矿物质溶解腐蚀了。 地质、物理、生物学家共同研究得出: 1、腐蚀是以格子为单位的,只能一整格被腐蚀; 2、腐蚀是分步进行的,每一步只有一格被腐蚀; 3、如果去掉一个格子后躯体不连通了,那么这个格子当前不会被腐蚀; 4、如果一个格子的左边邻格和右边邻格都还没被腐蚀,那么这个格子当前不会被腐蚀; 5、与头相邻的格子不能全部被腐蚀,与尾相邻的格子不能全部被腐蚀; 倘若满足上面五条,我们仍然可以用(n,L’1,L’2,..,L’n,R’1,R’2,..R’n)来描述一个化石里头的千年虫的形态。其中L’i≤R’i。 例如下图:
BZOJ1496-3
现在你的任务是,输入一个化石里的千年虫的描述A,找一个满足理论模型的千年虫的描述B,使得B可以通过腐蚀过程得以变为A,且由B转化为A的代价(须被腐蚀的格子数)最少。输出此最小代价。

Tag

动态规划

题目大意

给定数列,求增加最少的数量使得数列变成梳子状的数列并且首尾皆为凹。

解决思路

题目说的非常复杂,简化题意后得到求花费最少的代价使得序列变成一个类似梳子的序列且头尾都是凹的。考虑到两边的其实是互不影响的,所以分成两次来考虑。
设\(F[i][j][k]\) 表示当前处理到第i个数字,当前数字为j,当前凹凸性为k最小代价。则F[i][j][k]可以由F[i-1][p][k]或F[i-1][p][k^1]转移过来,具体要看p与j的关系。论文证明,每一次p和j的取值其实是在一定范围内的,即在当前行的上三行下三行范围内,原数列值到原数列值+3这个范围内的数,那么可行的转移状态就剩下常数个了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1000100;
const int inf=47483647;

int n;
int L[maxN],R[maxN];
ll H[maxN];
ll F[2][maxN][2],Pos[2][maxN],Cnt[2];

ll Calc();

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>L[i]>>R[i];
    for (int i=1;i<=n;i++) H[i]=R[i];
    ll Ans=0;
    Ans+=Calc();//分为两次计算
    for (int i=1;i<=n;i++) H[i]=maxN-L[i];
    Ans+=Calc();
    cout<<Ans<<endl;
    return 0;
}

ll Calc()
{
    Cnt[1]=0;//求出第一个数可能的所有状态
    for (int i=1;i<=3;i++)
        for (int j=H[i];j<=H[i]+3;j++)
            if (j>=H[1]) Pos[1][++Cnt[1]]=j;
    mem(F,63);//得到第一个数每一种状态对应的代价
    for (int i=1;i<=Cnt[1];i++) F[1][i][0]=Pos[1][i]-H[1];
    int now=1;
    for (int i=2;i<=n;i++)//从第二个数开始计算
    {
        now^=1;Cnt[now]=0;
        int l=max(1,i-2),r=min(n,i+2);//枚举的上下界
        for (int j=l;j<=r;j++)//得到当前这一个数的所有可能状态
            for (int k=H[j];k<=H[j]+2;k++)
                if (k>=H[i]) Pos[now][++Cnt[now]]=k;
        for (int j=1;j<=Cnt[now];j++)//枚举这一次的状态
        {
            F[now][j][0]=F[now][j][1]=inf;
            for (int k=1;k<=Cnt[now^1];k++)//枚举当前这个状态由上一行的哪一个转过来
                if (Pos[now][j]>Pos[now^1][k]) F[now][j][1]=min(F[now][j][1],F[now^1][k][0]);//上一个数大,那就是上一个数凸转移到这一个数凹
                else if (Pos[now][j]<Pos[now^1][k]) F[now][j][0]=min(F[now][j][0],F[now^1][k][1]);//上一个数小,那就是上一个数凹转移到这一个数凸
                else//相同时,凹凸皆可以转移
                {
                    F[now][j][0]=min(F[now][j][0],F[now^1][k][0]);
                    F[now][j][1]=min(F[now][j][1],F[now^1][k][1]);
                }
            F[now][j][0]+=Pos[now][j]-H[i];
            F[now][j][1]+=Pos[now][j]-H[i];
        }
    }
    ll Ret=inf;//取最优值
    for (int i=1;i<=Cnt[now];i++) Ret=min(Ret,F[now][i][0]);
    return Ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1496/Luogu2703][NOI2006]千年虫(动态规划)


HNCJ OIer