本文主要是介绍POJ-1952 最长下降子序列 + 方案数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求最长下降子序列 简单 就是求方案数比较麻烦点 看了别人的解题报考才懂也对最长**子序列的理解更深一步
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 5005;
int n;
int price[maxn],len[maxn],count[maxn]; //len[i]记录到i最长下降序列数 count记录方案数
int maxnum,max_count;
int main()
{//freopen("data.in","r",stdin);while( scanf("%d",&n) != EOF ){for( int i=0; i < n; i ++ )scanf("%d",&price[i] );maxnum = -1; for( int i = 0; i < n; i++ ) { count[i] = 1; len[i] = 1; //初始化for( int j=i-1; j>=0; j-- ) //找出第i项与i-1项匹配出最长的下降序列{ if( price[j] > price[i] ){if( len[j] + 1 > len[i] ){len[i] = len[j]+1;count[i] = count[j];}else if( ( len[j] + 1 ) == len[i] ) //下降序列数相同 方案数相加count[i] += count[j];}else if( price[j] == price[i]) //去重{ if( len[i] == 1 )count[i]=0;break;} }if( len[i] > maxnum ) //找出最长下降序列数maxnum = len[i]; }max_count = 0;for( int i=0; i < n; i ++ ) //统计方案数{if( len[i] == maxnum )max_count += count[i];}printf("%d %d\n",maxnum,max_count);}return 0;
}
这篇关于POJ-1952 最长下降子序列 + 方案数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
