Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1632
Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1278
其实两道题是同一个题，都是LIS类型。
刚开始是做1278，但是出来后过不了，便试了一下1632，结果过了。
网上找了下原始版的LIS代码，看不出个所以然。
找JL帮忙，他给了个数据，没过。
我一看，把等号去掉，轻松就AC了。
结论就是，有些OJ的CASE很水= =（后来发现其实不是CASE水，而是我水……题意确实有点不同……）
经典的LIS自己可以去找下看看，代码如下：
#include<iostream>using namespace std;
int a[1005];int dp[1005];int main(){ int n,i,j,ans,max; while(cin>>n&&n) { for(i=1;i<=n;i++) cin>>a[i]; max=0; for(i=1;i<=n;i++) { dp[i]=1; for(j=1;j<=i-1;j++) { if(a[j]>=a[i]&&dp[i]<=dp[j]+1) dp[i]=dp[j]+1; } if(dp[i]>max) max=dp[i]; } cout<<max<<endl; } return 0;}
我其实是之前看过了别人文章的介绍所以用了另一种方法。
他的那种是新建一个数组然后记录序列长度数，而我的是直接在原来的数据数组里操作。
初始序列长度为0。
对于每一个数都跟序列长度以内的数比较，如果刚好比某一个数大，则把它覆盖到上面去。
如果超出序列长度还没找到比他小的数，则把这个数添加到序列的尾部并使长度加一。
这个算法对比上一个可以节省很多对比的次数。
所以结果出来后是453MS和31MS的差距。
赞一下自己~也赞一下JL~。
以下贴代码：
#include <iostream>using namespace std;int main(){ int ct[1005],num; int n,i,x,j; while(scanf("%d", &n)!=EOF) { if (n==0) break; num = 0; for (i=0; i<n; i++) { scanf("%d", &ct[i]); } for (i=0; i<n; i++) { x = ct[i]; for (j=0; j<num; j++) { if (x>=ct[j])//这里如果使用>=则为严格单调递减，否则为单调非递增 { ct[j] = x; break; } } if (j==num) { ct[num] = x; num++; } } printf("%d/n", num); } return 0;}
今天开始学习DP，不过乱找的几道题都看不出个所以然。哎~
继续努力啦！！
