Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

谁能告诉我这段代码错在哪儿?

Posted by bearxy39 at 2004-10-29 14:51:39 on Problem 1952
//我wa到想自杀了~~~
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;

int dp[5001],N,data[5001];
bool notin(vector<int> cc,int a)
{
	for(int i=0;i<cc.size();i++)
		if(cc[i]==a) return 0;
	return 1;
}
int main()
{
	while(cin>>N)
	{
		data[0]=2100000000;
		int i,j;
		for(i=1;i<=N;i++)
			scanf("%d",&data[i]);
		int max=0;
		dp[0]=0;
		for(i=1;i<=N;i++)
		{
			int m=0;
			for(j=i-1;j>=0;j--)
				if(dp[j]+1>m&&data[i]<data[j])
					m=dp[j]+1;
			dp[i]=m;
			if(m>max) max=m;
		}
		int ans=0;
		int cases[5001];
		for(i=1;i<=N;i++)
		{
			if(dp[i]==1) cases[i]=1;
			else
			{
				vector<int> cc;
				cases[i]=0;
				for(j=i-1;j>0;j--)
				{
					if(dp[j]==dp[i]-1&&data[j]>data[i]&&notin(cc,data[j]))
					{
						cc.push_back(data[j]);
						cases[i]+=cases[j];
					}
				}
			}
		}
		vector<int> last;
		for(i=1;i<=N;i++)
		{
			if(dp[i]==max&&notin(last,data[i]))
			{
				last.push_back(data[i]);
				ans+=cases[i];
			}
		}
		cout<<max<<" "<<ans<<endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator