NYoj 17 单调递增最长子序列[典型动态规划1]

本文主要是介绍NYoj 17 单调递增最长子序列[典型动态规划1]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*NYoj 17 单调递增最长子序列典型动态规划1.
*/
#include<iostream>
#include<memory.h>
#include<string.h>
#define max(a,b) a>b?a:b
using namespace std;
int main()
{int T;cin>>T;while(T--){char a[10002];cin>>a;int dp[10002],Max=0,len=strlen(a);memset(dp,0,sizeof(dp));//同样这里的每一个字母都可以作为单调递增序列的第一个字母.for(int i=0;i<len;i++)  //但是此处赋值为1，处于时间复杂度的考虑，最后+1即可.{for(int j=i;j>=0;j--)if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);//do[i]为当前递增序列的最优解.Max=max(Max,dp[i]);}cout<<Max+1<<endl;}
}

HuNanOJ上有看见这道题。就又做了下。很是容易。

#include<cstdio>
#include<cstring>
#define Max(a,b) a>b?a:b
using namespace std;const int N=1005;int main()
{int n;while(~scanf("%d",&n)){int a[N],dp[N],max=0;memset(dp,0,sizeof(dp));for(int i=0;i<n;i++)scanf("%d",&a[i]);for(int i=0;i<n;i++){for(int j=i;j>=0;j--)if(a[i]>a[j]) dp[i]=Max(dp[i],dp[j])+1;max=Max(dp[i],max);}printf("%d\n",max+1);}return 0;
}

后来，我就想时间复杂度的问题，很是郁闷N^2的复杂度，这时间上就太弱了。后来看了后来的那道题，有一个二分的方法。这种方法在时间相当的占优势。所以以后做类似的问题就不要用这种弱渣型的时间复杂度了。

这篇关于NYoj 17 单调递增最长子序列[典型动态规划1]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---