Bubble Sort Graph CodeForces - 340D || 最长不…
2018-06-17 21:53:38来源:未知 阅读 ()
Bubble Sort Graph CodeForces - 340D
题意:
给出一个n个数的数列,建一个只有n个结点没有边的无向图,对数列进行冒泡排序,每交换一对位置在(i,j)的数在点i和点j间连一条边。排序完后,求得到图的最大独立集。
解释:
最初想到的是图的最大独立集,认为不能解,于是就没辙了...
然而应当仔细分析题目(不容易想到):题意很容易知道是在每一对逆序对间连一条边。也就是说,对于a[i],向a[i]右侧比其小的和a[i]左侧比其大的都要连一条边。也就是说,只要选了结点i,那么a[i]右侧比其小的和a[i]左侧比其大的结点都不能选。也就是说,对于某一个选出的数a[i],左侧只可能选出比其小的,右侧只可能选出比其大的。也就是要求最长上升子序列。
ans[i]记录长度为k的LIS最末元素位置的最小值
2 1 5 3 6 4 8 9 7 8 9
1:
1
2:
2
3:
2,3(1,5)
4:
2,4(1,3)
5:
2,4,5(1,3,6)
6:
2,4,6(1,3,4)
7:
2,4,6,7(1,3,4,8)
8:
2,4,6,7,8(1,3,4,8,9)
9:
2,4,6,9,8(1,3,4,7,9)
10:
2,4,6,9,10(1,3,4,7,8)
11:
2,4,6,9,11(1,3,4,7,8,9)
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int n,a[100100]; 5 int s[100100]; 6 int main() 7 { 8 int i; 9 scanf("%d",&n); 10 for(i=1;i<=n;i++) 11 scanf("%d",&a[i]); 12 for(i=1;i<=n;i++) 13 { 14 if(a[i]>s[s[0]]) 15 s[++s[0]]=a[i]; 16 else 17 *upper_bound(s+1,s+s[0]+1,a[i])=a[i]; 18 } 19 printf("%d",s[0]); 20 return 0; 21 }
补一份最长严格上升子序列(倒序输出)的:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int n,a[100100]; 6 int s[100100],f[100100],len; 7 int main() 8 { 9 int i,j,t; 10 scanf("%d",&n); 11 for(i=1;i<=n;i++) 12 scanf("%d",&a[i]); 13 memset(s,0x3f,sizeof(s)); 14 for(i=1;i<=n;i++) 15 { 16 t=lower_bound(s+1,s+len+1,a[i])-s; 17 s[t]=a[i]; 18 f[i]=t; 19 len=max(len,t); 20 } 21 printf("%d\n",len); 22 for(i=n,j=len;i>=1;i--) 23 if(f[i]==j) 24 { 25 printf("%d ",a[i]); 26 j--; 27 } 28 return 0; 29 }
不下降:将lower_bound改成upper_bound
upd 2018-3-30:
https://blog.csdn.net/u013665921/article/details/39856659
例如最长不下降子序列:
如果存在j<i且a[j]<=a[i]
则dp[i]=max{dp[j]}(j<i且a[j]<=a[i])+1
否则dp[i]=1
所以对值域开一个线段树就可以O(nlogn)了,输出方案也容易
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:const
- CountingSort(计数排序)原理及C++代码实现 2020-01-14
- MergeSort(归并排序)原理及C++代码实现 2020-01-14
- InsertionSort(插入排序)原理及C++代码实现 2020-01-14
- P5200 [USACO19JAN]Sleepy Cow Sorting 2019-08-26
- POJ 2299-Ultra-QuickSort-线段树的两种建树方式 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash