最少拦截系统（经典LIS DP）

传送门

最少拦截系统　HDU1257

题意：求最长上升子序列LIS的长度；
1、O(n^2) DP：

#include
using namespace std;int a[100010];
int dp[100010]; //dp[i] 代表以a[i] 结尾的子串的最长上升子序列的长度
int  main()
{int n;while(cin>>n){for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){dp[i] = 1;	//边界,只有自己for(int j=1;j<i;j++){if(a[j]<a[i]) dp[i] = max(dp[i],dp[j]+1);}ans = max(dp[i],ans);	//取每个子序列的最值}cout<<ans<<endl;}return 0;
} 

DP输出路径:

#include
using namespace std;
const int N = 1010;int a[N],dp[N];
int g[N];  //记录当前状态是从哪个状态转移来的
int main()
{int n; cin>>n;int ans = 1;for(int i=1;i<=n;i++){cin>>a[i];dp[i] = 1; g[i] = 0;for(int j=1;j<i;j++){if(a[j]<a[i])if(dp[i]<dp[j]+1){dp[i] = dp[j]+1;g[i] = j;	//记录每个dp[i] 是从哪个状态转移过来的}}}int k = 1;for(int i=1;i<=n;i++)if(dp[i] > dp[k]) k = i;	//寻找最长的子序列printf("%d\n",dp[k]);for(int len=dp[k];len>=1;len--){	//倒序输出路径 printf("%d ",a[k]);k = g[k];}return 0;} 

2、O(nlogn) 利用二分：

#include
using namespace std;int a[100010];
int low[100010]; //low[i] 代表以a[i] 结尾的子串的最长上升子序列的结尾的最小值 
int  main()
{int n;while(cin>>n){for(int i=0;i<n;i++) cin>>a[i];int ans=1;	//最长上升子序列长度； low[ans] = a[0];  // 最长上升子序列 ;  for(int i=1;i<n;i++){if(low[ans] < a[i]) low[++ans] = a[i];  // 最长不下降子序列 换成 <= else {int j = lower_bound(low+1,low+ans+1,a[i]) - low ;  //最长不下降子序列 换成upper_bound()即可low[j] = a[i] ;}}
//		for(int i=1;i<=ans;i++) cout<
//		cout<cout<<ans<<endl;}return 0;
}

最近又发现了这种写法，不错~

#include
#include
#includeusing namespace std;int a[100010];
int low[100010];  //存目标子序列 
int  main()
{int n;cin>>n; for(int i=0;i<n;i++) cin>>a[i];int ans=0;memset(low,0x3f,sizeof low); 	//都初始化INF 以便于找不到大于等于x的值时返回新拓展的位置for(int i=0;i<n;i++){int pos = lower_bound(low+1,low+n+1,a[i]) - low ;	//注意区别，这里在 1~n内二分low[pos] = a[i];ans = max(ans,pos);}
//	for(int i=1;i<=ans;i++) cout<
//	cout<cout<<ans<<endl;return 0;
}

手动二分

#include 
using namespace std;
const int N = 1e5 + 9;
int f[N], a[N];   //多组无需清空
int n;
int find(int l, int r, int x) {   //返回第一个大于等于x的下标，否则返回右边界while (l < r) {int mid = (l + r) / 2;if (f[mid] < x) {l = mid + 1;} else {r = mid;}}return l;
}int main() 
{while(~scanf("%d", &n)){for (int i = 0; i < n; i++) scanf("%d", a + i);int len = 0;for (int i = 0; i < n; i++) {int k = find(0,len,a[i]);f[k] = a[i];if (k == len) len++;}printf("%d\n", len);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！