bzoj 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛【dp+树状数组+hash】

最长上升子序列。虽然数据可以直接n方但是另写了个nlogn的

转移：f[i]=max(f[j]+1)(a[j]<a[i])

O(n^2)

#include<iostream>

#include<cstdio>

using namespace std;

const int N=5005;

int n,a[N],f[N],ans;

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

int main()

{

	n=read();

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

		a[i]=read();

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

	{

		for(int j=0;j<i;j++)

			if(a[j]<a[i]&&f[j]+1>f[i])

				f[i]=f[j]+1;

		ans=max(ans,f[i]);

	}

	printf("%d\n",ans);

	return 0;

}

O(nlogn)树状数组+hash

#include<iostream>

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

const int N=5005;

int n,a[N],f[N],ans,g[N],t[N];

map<int,int>mp;

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

inline int lb(int x)

{

	return x&(-x);

}

void update(int x,int v)

{

	for(int i=x;i<=n;i+=lb(i))

		t[i]=max(t[i],v);

}

int ques(int x)

{

	int re=0;

	for(int i=x;i>=1;i-=lb(i))

		re=max(re,t[i]);

	return re;

}

int main()

{

	n=read();

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

		a[i]=g[i]=read();

	sort(g+1,g+1+n);

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

		mp[g[i]]=i;

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

		a[i]=mp[a[i]];

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

	{

		f[i]=ques(a[i]-1)+1;

		update(a[i],f[i]);

		ans=max(ans,f[i]);

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛【dp+树状数组+hash】

最新文章

热门文章