6
4 3 4 1 3 1

======
答案应该是3 1，最长长度为3，只有一种情况：4,3,1，我也是计数计了好久都没找到正确的方法计正确。网上找到了一个很简洁的方法，下面是我AC的代码，我是从右到左算最大升序列

#include <iostream>
#include <fstream>
using namespace std;
const int N = 5001;
int n, dp_len[N], a[N], ans_len, dp_time[N],ans_time;

int main()
{
	fstream fin("1952.txt");
	fin>>n;
	for(int i = 1; i <= n; i++)
		fin>>a[i];
	ans_len = 1; dp_len[n] = 1; dp_time[n] = 1;
	for(int i = n-1; i >= 1; i--)
	{
		dp_len[i] = 1; dp_time[i] = 1;
		for(int j = i+1; j <= n; j++)
			if(a[i] > a[j])
			{
				if(dp_len[j] + 1 > dp_len[i])
				{
					dp_len[i] = dp_len[j]+1; dp_time[i] = dp_time[j];
				}
				else if(dp_len[j]+1 == dp_len[i])
					dp_time[i] += dp_time[j];
			}
			else if(a[i] == a[j])//key point!
			{
				if(dp_len[i] == 1)
					dp_time[i] = 0;
				break;
			}
	///////////////////////////
		if(dp_len[i] > ans_len)
			ans_len = dp_len[i];
	}
	///////////////////////////
	ans_time = 0;
	for(int i = 1; i <= n; i++)
		if(dp_len[i] == ans_len)
			ans_time += dp_time[i];
	cout<<ans_len<<" "<<ans_time<<endl;
	return 0;
}

• Re:大家都试试这个数据 (262) temp_ptr 2011-10-07 14:30:50