Home > Old Blog Posts > USACO 4.3.1 Buy Low Buy Lower

USACO 4.3.1 Buy Low Buy Lower


第一问很容易 就是裸的最长下降子序列

第二问有很多种方法处理 这里只阐述一种:

对于0<=j<i,若a[j]>a[i]且f[j]+1=f[i],则sum[i]=sum[i]+sum[j]

为处理重复,可设一数组p,p[i]代表大于i且a[j]=a[i]的j的最小值,在计算时,当且仅当p[j]=0或p[j]>=i时才予以考虑,否则直接跳过

由于此题数据规模很大,计算时需用到高精

/*
ID: dementr1
PROG: buylow
LANG: C++
*/
#include
#include
#define MAX 30
#define MAXN 5001
using namespace std;
ifstream fin("buylow.in");
ofstream fout("buylow.out");
int n,a[MAXN],f[MAXN],ans[MAXN][MAX+10],answer[2],next[MAXN];
void init()
{
	int i,j;
	fin>>n;
	for(i=0;i>a[i];
	a[n++]=0;
	for(i=0;i=0;i--)
	{
		if(a[i]b[i]) break;
	}
	for(i=MAX-1;i>=0;i--)
		b[i]=a[i];
}
void print(int p[])
{
	int i,j;
	for(i=MAX-1;i>=0;i--)
		if(p[i]>0) break;
	for(j=i;j>=1;j--)
		fout<
0)
	{
		if(p[0]<10000000) fout<<0;
		if(p[0]<1000000) fout<<0;
		if(p[0]<100000) fout<<0;
		if(p[0]<10000) fout<<0;
		if(p[0]<1000) fout<<0;
		if(p[0]<100) fout<<0;
		if(p[0]<10) fout<<0;
	}
	fout<
<f[i])
				f[i]=f[j]+1;
		if(f[i]>maxf) maxf=f[i];
		bool flag=false;
		for(j=i-1;j>=0;j--)
		{
			if(a[j]>a[i]&&f[j]+1==f[i]&&(next[j]>=i||next[j]==0))
			{
				flag=true;
				add(ans[i],ans[j]);
			}
		}
		if(!flag) ans[i][0]=1;
		max(ans[i],answer);
	}
	maxf--;
	fout<<<" ";
	print(ans[n-1]);
}
int main()
{
	init();
	dp();
	return 0;
}
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: