首页 > 代码库 > HDU 2610 (自己完全找不到思路) Sequence one

HDU 2610 (自己完全找不到思路) Sequence one

2024-07-18 01:00:10   211人阅读

搜索虐我千百遍，我待搜索。。。好吧，我还木有初恋

题意：

我开始理解题意就理解偏了，Orz

题中有n个元素构成的序列，求出前p个非递减子序列。子序列是先按长度排序的，然后按原序列先后位置排序的。

这里的非递减是指子序列中从左到右元素大小的值不减，对，就是这我理解错了。

如果p>所有符合要求的子序列的个数，那么输出所有的子序列

 

这道题完全是参照这个大神的博客的代码A过的

http://www.cnblogs.com/newpanderking/archive/2012/10/11/2719941.html

 

思路：

按子序列的长度从1到n-1去搜，在搜长为len的子序列时，也是从左到右的元素逐个搜索，当搜索到的元素的个数满足len时，便输出一个子序列。

判重：

①当我们搜索子序列的第一个元素的时候，只需要和该元素之前的比较，如果有重复的话不再搜索

②当我们搜索子序列的第i个元素的时候，将要比较的元素j与 (搜到的子序列中第i-1个元素， 元素j)这个开区间的元素比较，如果有重复的话不再搜索

剪枝：

flag作为一个标记，每次搜索长度为i的子序列的时候将其赋值为false，找到一个长为i的子序列就赋值为true。

试想，如果长为i的子序列都不曾找到，那么一定不会存在长为i+1的子序列的。

 

再次膜拜一下高冷的代码君：

 1 #define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 struct Tem 8 { 9     int n, pos;10 }tem[1010];11 int n, p, len, cnt, num[1010];12 bool flag;13 14 bool check(int s, int e)15 {16     for(int i = s + 1; i < e; ++i)17         if(num[i] == num[e])18             return false;19     return true;20 }21 22 void OutPut(int len)23 {24     for(int i = 0; i < len - 1; ++i)25         printf("%d ", tem[i].n);26     printf("%d\n", tem[len - 1].n);27 }28 29 void DFS(int dep, int pos)30 {31     if(cnt >= p)32         return;33     if(dep == len)34     {35         ++cnt;36         flag = true;37         OutPut(len);38         return;39     }40     for(int i = pos; i < n; ++i)41     {42         if(dep == 0 || tem[dep - 1].n <= num[i])43         {44             if(dep == 0 && !check(-1, i))45                 continue;46             if(dep != 0 && !check(tem[dep - 1].pos, i))47                 continue;48             tem[dep].n = num[i];49             tem[dep].pos = i;50             DFS(dep + 1, i + 1);51         }52     }53     return;54 }55 56 int main(void)57 {58     #ifdef LOCAL59         freopen("2610in.txt", "r", stdin);60     #endif61 62     while(scanf("%d%d", &n, &p) == 2)63     {64         for(int i = 0; i < n; ++i)65             scanf("%d", &num[i]);66         cnt = 0;67         for(int i = 1; i < n; ++i)68         {69             flag = false;70             len = i;71             DFS(0, 0);72             if(cnt >= p || !flag)73                 break;74         }75         printf("\n");76     }77     return 0;78 }
代码君

 


联系
我们