现在的位置: 首页 > 综合 > 正文

ZOJ 1108 白老鼠越大越慢

2012年10月02日 ⁄ 综合 ⁄ 共 2193字 ⁄ 字号 评论关闭

//////////////////////////////////////////////////////////
//FatMouse's Speed 白老鼠越大越慢
//利用dp,与DNA序列相似

 

#include<iostream>
using namespace std;
int st[1001][2], output[1001];   

class Mouse
{
public:
    int size;
    int speed;
    int No;

    bool operator<=(Mouse a)
    {
        return (size<=a.size);
    }

};

 

///////////////////////////////////////////////////////////
template<class type>
void Merge(type c[],type d[],int l,int m ,int r)
{
    int i=l,j=m+1,k=l,q;
    while((i<=m) && (j<=r))
    {
        if(c[i]<=c[j])
            d[k++]=c[i++];
        else
            d[k++]=c[j++];
    }
    if(j>r)
        for(q=i;q<=m;q++)
            d[k++]=c[q];
    else
        for(q=j;q<=r;q++)
            d[k++]=c[q];    
}

 

////////////////////////////////////////////////////////////
template <class type>
void MergePass(type x[],type y[],int s,int n)
{
    int j,i=0;
    while(i+2*s<=n)
    {
        Merge(x,y,i,i+s-1,i+2*s-1);
        i+=2*s;
    }
    if(i+s<n)
        Merge(x,y,i,i+s-1,n-1);
    else
        for(j=i;j<n;j++)
            y[j]=x[j];
}

 

////////////////////////////////////////////////////////////
template <class type>
void MergeSort(type a[],int n)
{
    type *b=new type[n];
    int s=1;
    while(s<n)
    {
        MergePass(a,b,s,n);
        s*=2;
        MergePass(b,a,s,n);
        s*=2;
    }
}

 

 

///////////////////////////////////////////////////////////////

Mouse mice[1001];

int main()
{
    int i,j,len,maxlever,max,post,state;
    mice[0].size=0;
    mice[0].speed=20000;
    mice[0].No=0;
    i=1;
    while((cin>>mice[i].size)!=0)
    {
        cin>>mice[i].speed;
        mice[i].No=i;
        i++;
    }
    len=i;                 //此长度非原来长度,增加了mice[0]
    MergeSort(mice,len);   

    st[0][0]=-1;
    st[0][1]=0;
    for(i=1;i<len;i++)
    {
        maxlever=-1;
        for(j=0;j<i;j++)
        {
            if(mice[i].size>mice[j].size && mice[i].speed<mice[j].speed && st[j][1]>maxlever)
            {                                          //此处保证序列严格递增、递减
                maxlever=st[j][1];
                state=j;
            }            
        }
        st[i][1]=maxlever+1;
        st[i][0]=state;
    }

    post=0;
    max=0;
    for(i=1;i<len;i++)
        if(max<st[i][1])
        {
            max=st[i][1];
            post=i;
        }

    i=0;
    while(post!=0)
    {
        output[i]=mice[post].No;
        post=st[post][0];
        i++;
    }
    cout<<max<<endl;
    for(j=i-1;j>=0;j--)
        cout<<output[j]<<endl;

    return 0;
}

 

抱歉!评论已关闭.