当前位置 博文首页 > Keven_11的博客:C++题解:冒泡排序生成图
?????目录
题目?
题解
- ?1000ms
- ?131072K
蒜头最近学习了冒泡排序,他用冒泡序列把一个排列?a1?, a2??……?an??排成升序。
他觉得冒泡排序太无聊了,他想在冒泡排序的基础上构建一张图,初始的时候图有?n?个顶点?0?条边。他在冒泡排序过程中嵌入一些生成图上边的代码,代码框架如下。
int bubbleSortGraph(int n) { // 建一个 n 个点 0 条边的图 G bool swapped = false; do { swapped = false; for (int i = 1; i < n; i++) { if (a[i] > a[i + 1]) { // 在 a[i] 和 a[i + 1] 之间连一条边 swap(a[i], a[i + 1]); swapped = true; } } } while (swapped) /* 重复执行直到不再出现交换*/ }
图上的一个独立集定义为图的顶点集?V?的一个子集?V′,V'?中任意任意两个顶点之间都没有边存在。最大独立集是指点数最多的独立集。
给定排列?a,求出蒜头生成的图上的最大独立集。
输入格式
输入第一行一个整数 n(2≤n≤1000)。
接下里一行输入?n?个整数??a1?, a2??……?an??(1≤ai?≤n)。
输出格式
输出一个整数表示最大独立集的点的个数。
输出时每行末尾的多余空格,不影响答案正确性
要求使用「文件输入输出」的方式解题,输入文件为?
sort.in
,输出文件为?sort.out
样例输入
3 3 1 2样例输出
2题解:
知识点:最长上升子序列
分析:这道题的题面很容易把人带偏,对于任意的?i < j,如果?a[i] > a[j],那么?a[i] 和?a[j]?之间必然会有一条边。所以一个独立集对应一个上升子序列,那么最大独立集就对应最长上升子序列。注意,不是最长不下降子序列,这是个坑点,原因是集合既有互异性。
代码:
cs#include<iostream> #include<cstdio> #include<algorithm> #define _for(i,a,b) for (int i=(a);i<=(b);i++) using namespace std; const int N=1e3+5; int a[N],dp[N],ans=-0x7fffffff; int main(){ freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); int n; scanf("%d",&n); _for(i,1,n){ scanf("%d",&a[i]); dp[i]=1;//最长上升子序列,这里做了个小优化 _for(j,1,i){ if (a[i]>a[j]){ dp[i]=max(dp[i],dp[j]+1); } ans=max(dp[i],ans); } } printf("%d",ans); return 0; }
下一篇:没有了