1576 最长严格上升子序列
时间限制: 1 s 空间限制: 256000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 给一个数组a1, a2 ... an，找到最长的上升降子序列ab1b2< .. bk，其中b1
输入描述 Input Description 第一行，一个整数N。
第二行 ，N个整数（N < = 5000）
输出描述 Output Description 输出K的极大值，即最长不下降子序列的长度
样例输入 Sample Input 5
9 3 6 2 7
样例输出 Sample Output 3
数据范围及提示 Data Size & Hint 【样例解释】
最长不下降子序列为3,6,7
解题思路：
应该算是序列型DP的最入门的写法了，严格上升子序列的写法有很多种，我用的这个还算是比较好理解的，题目中做了别样的处理就是为了防止出现某个序列，这个序列中的所有元素都是相同的，那么输出的就是1。。。
【CODE[VS]|Code[vs] 1576 最长严格上升子序列】代码：
# include
# includeusing namespace std;
# define MAX 100000+4int value[MAX];
int dp[MAX];
int main(void)
{
int n;
while ( cin>>n )
{
int flag = 0;
double sum = 0;
for ( int i = 0;
i < n;
i++ )
{
cin>>value[i];
sum+=value[i];
dp[i] = 1;
}
int tag = 0;
double avg = (1.0*sum)/n;
for ( int i = 0;
i < n;
i++ )
{
if ( value[i] == avg )
tag++;
}
if ( tag == n )
{
flag = 1;
}
int ans = 0;
for ( int i = 0;
i < n;
i++ )
{
for ( int j = i+1;
j < n;
j++ )
{
if ( value[j] > value[i] )
{
dp[j] = max( dp[j],dp[i]+1 );
ans = max( ans,dp[j] );
}
}
}
if ( flag )
{
cout<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
