--- 恢复内容开始 ---
1. 先上个基础的全排列
- #include<iostream>
- #include<cstring>
- using namespace std;
- const int maxn=1e3;
- int vis[maxn];
- int p[maxn];
- int n;
- int t=0;
- void dfs(int x)
- {
- if(x==n+1)
- {
- for(int i=1;i<=n;i++)
- cout<<p[i]<<" ";
- cout<<endl;
- return ;
- }
- for(int i=1;i<=n;i++)
- {
- if(!vis[i])
- {
- vis[i]=1;
- p[x]=i;
- dfs(x+1);
- vis[i]=0;
- }
- }
- }
- int main()
- {
- while(cin>>n)
- {
- memset(vis,0,sizeof(vis));
- dfs(1);
- }
- }
- 2. HDU2614 http://acm.hdu.edu.cn/showproblem.php?pid=2614
这是个什么鬼题, 依然不太明白题意, Hint 部分还带有误导性. 反正就是尽量让解题时间变长, 找最长解题数目. 对于 Tij, 如果符合条件, vis[j] 通通不能再用.... 但是代码是很简单, 基本的 dfs 模板操作.
- #include<iostream>
- #include<cstring>
- using namespace std;
- const int maxn=20;
- int e[maxn][maxn];
- int vis[maxn*maxn];
- int ans;
- int k,n;
- void dfs(int now,int time,int k)
- {
- for(int i=0;i<n;i++)
- {
- if(!vis[i]&&e[now][i]>=time)
- {
- vis[i]=1;
- dfs(i,e[now][i],k+1);
- vis[i]=0;
- }
- }
- ans=max(ans,k);
- }
- int main()
- {
- while(cin>>n)
- {
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- cin>>e[i][j];
- memset(vis,0,sizeof(vis));
- vis[0]=1;
- ans=1;
- dfs(0,0,1);
- cout<<ans<<endl;
- }
- }
5974: [递归入门] 组合 + 判断素数 http://codeup.cn/problem.php?id=5974
题目描述
已知 n 个整数 b1,b2,...,bn
以及一个整数 k(k<n).
从 n 个整数中任选 k 个整数相加, 可分别得到一系列的和.
例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时, 可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34.
现在, 要求你计算出和为素数共有多少种.
例如上例, 只有一种的和为素数: 3+7+19=29.
输入
第一行两个整数: n , k (1<=n<=20,k<n)
第二行 n 个整数: x1,x2,...,xn (1<=xi<=5000000)
输出
一个整数 (满足条件的方案数).
样例输入
- 4 3
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- using namespace std;
- const int maxn=200;
- int vis[maxn];
- int a[maxn];
- int num[maxn];
- int n,k;
- int ans=0;
- int sum=0;
- int ac(int x)
- {
- if(x<=1)
- return 0;
- for(int i=2;i*i<=x;i++)
- {
- if(x%i==0)
- return 0;
- }
- return 1;
- }
- void dfs(int ind)
- {
- if(ind==k+1)
- {
- if(ac(sum))
- ans++;
- /* for(int i=1;i<=k;i++)
- cout<<num[i]<<" ";*/
- cout<<endl;
- return ;
- }
- for(int i=1;i<=n;i++)
- {
- if(!vis[i]&&i>num[ind-1])
- {
- sum+=a[i];
- num[ind]=i;
- vis[i]=1;
- dfs(ind+1);
- vis[i]=0;
- sum-=a[i];
- }
- }
- }
- int main()
- {
- cin>>n>>k;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- num[i]=i;
- }
- dfs(1);
- cout<<ans<<endl;
- return 0;
- }
- 3 7 12 19
样例输出
1
dfs 入门题
第一次 T 了, 因为会出现重复计算, 效率低. 所以参照题解加入了 num 数组, 进行下标记录, i>num[ind-1], 保证方向是正向的. sum 记得加完在减掉回溯.
来源: http://www.bubuko.com/infodetail-3285315.html