【POJ2533】Longest Ordered Subsequence

梦里梦外; 2022-07-19 08:58 175阅读 0赞

<table style="font-family:Simsun"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      Longest Ordered Subsequence 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;47040</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;20904</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Description</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      A numeric sequence of&nbsp; 
     <em>a<sub>i</sub></em>&nbsp;is ordered if&nbsp; 
     <em>a<sub>1</sub></em>&nbsp;&lt;&nbsp; 
     <em>a<sub>2</sub></em>&nbsp;&lt; ... &lt;&nbsp; 
     <em>a<sub>N</sub></em>. Let the subsequence of the given numeric sequence ( 
     <em>a<sub>1</sub></em>,&nbsp; 
     <em>a<sub>2</sub></em>, ...,&nbsp; 
     <em>a<sub>N</sub></em>) be any sequence ( 
     <em>a<sub>i<sub>1</sub></sub></em>,&nbsp; 
     <em>a<sub>i<sub>2</sub></sub></em>, ...,&nbsp; 
     <em>a<sub>i<sub>K</sub></sub></em>), where 1 &lt;=&nbsp; 
     <em>i<sub>1</sub></em>&nbsp;&lt;&nbsp; 
     <em>i<sub>2</sub></em>&nbsp;&lt; ... &lt;&nbsp; 
     <em>i<sub>K</sub></em>&nbsp;&lt;=&nbsp; 
     <em>N</em>. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). 
     <br> 
     <br> Your program, when given the numeric sequence, must find the length of its longest ordered subsequence. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Input</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 &lt;= N &lt;= 1000 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Output</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Input</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">7
1 7 3 5 9 4 8</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Output</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">4
</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Source</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=Northeastern+Europe+2002" style="text-decoration:none" rel="nofollow">Northeastern Europe 2002</a>, Far-Eastern Subregion 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

\[ [Submit][] \] \[ Go Back \] \[ [Status][] \] \[ [Discuss][] \]

简单动态规划，最长上升子序列基础模板题。虽是入门级，但也很重要，能够帮助理解LIS算法的基本原理，下面列出两种方法；

时间复杂度n^2:

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int a[1010],dp[1010];
    int main() {
    	int n;
    	while(scanf("%d",&n)!=EOF) {
    		for(int i=0; i<n; i++) {
    			scanf("%d",&a[i]),dp[i]=1;
    		}
    		if(!n){
    			printf("1\n");
    			continue;
    		}
    		int ans=1;
    		for(int i=1;i<n;i++){
    			for(int j=0;j<i;j++){
    				if(a[i]>a[j])
    				dp[i]=max(dp[i],dp[j]+1);
    			}
    			ans=max(ans,dp[i]);
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

\---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

以下nlogn复杂度这种挺巧妙的，以下是学习了大牛的写法后写下的代码理解一下就会发现其中的美。

尊重原创：[原创链接：http://blog.sina.com.cn/s/blog\_76344aef0100scyq.html][http_blog.sina.com.cn_s_blog_76344aef0100scyq.html]

先回顾经典的O(n^2)的动态规划算法，设A\[t\]表示序列中的第t个数，F\[t\]表示从1到t这一段中以t结尾的最长上升子序列的长度，初始时设F\[t\] = 0(t = 1, 2, ..., len(A))。则有动态规划方程：F\[t\] = max\{1, F\[j\] + 1\} (j = 1, 2, ..., t - 1, 且A\[j\] < A\[t\])。

根据F\[\]的值进行分类。对于F\[\]的每一个取值k，我们只需要保留满足F\[t\] = k的所有A\[t\]中的最小值。设D\[k\]记录这个值，即D\[k\] = min\{A\[t\]\} (F\[t\] = k)。

注意到D\[\]的两个特点：

(1)　D\[k\]的值是在整个计算过程中是单调不上升的。

(2)　D\[\]的值是有序的，即D\[1\] < D\[2\] < D\[3\] < ... < D\[n\]。

利用D\[\]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A\[t\]与D\[len\]。若A\[t\] > D\[len\]，则将A\[t\]接在D\[len\]后将得到一个更长的上升子序列，len = len + 1， D\[len\] = A\[t\]；否则，在D\[1\]..D\[len\]中，找到最大的j，满足D\[j\] < A\[t\]。令k = j + 1，则有D\[j\] < A\[t\] <= D\[k\]，将A\[t\]接在D\[j\]后将得到一个更长的上升子序列，同时更新D\[k\] = A\[t\]。最后，len即为所要求的最长上升子序列的长度。

poj 3903

nlogn复杂度：

</pre><pre name="code" class="cpp">#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    int a[1010],dp[1010];
    int sorce(int l,int r,int t) {
    	int mid=l+r>>1;
    	if(l==r) return l;
    	if(t>dp[mid]) return sorce(mid+1,r,t);
    	else return sorce(l,mid,t);
    }
    int main() {
    	int n;
    	while(scanf("%d",&n)!=EOF) {
    		for(int i=0; i<n; i++) {
    			scanf("%d",&a[i]);
    		}
    		dp[0]=-1;
    		int len=0,j;
    		for(int i=0; i<n; i++) {
    			if(a[i]>dp[len])
    				dp[++len]=a[i];
    			else {
    				j=sorce(1,len,a[i]);
    				dp[j]=a[i];
    			}
    		}
    		printf("%d\n",len);
    	}
    	return 0;
    }

[Submit]: http://poj.org/submit?problem_id=2533
[Status]: http://poj.org/problemstatus?problem_id=2533
[Discuss]: http://poj.org/bbs?problem_id=2533
[http_blog.sina.com.cn_s_blog_76344aef0100scyq.html]: http://blog.sina.com.cn/s/blog_76344aef0100scyq.html