0x02递推与递归例题
递归实现指数型枚举 （AcWing 92）
题目链接：递归实现指数型枚举
即给定一个n，输出1~n中的所有组合方案
①可以采取二进制状态压缩的方案
设 a=0，a<1<
点击查看代码
# include
using namespace std;
const int N=20;
int n;
int main()
{
cin>>n;
for(int i=0;i<(1<>j&1) cout< ②采用递归的方式。
AC代码：
点击查看代码
# include
using namespace std;
const int N=20;
int n,a[N];
void dfs(int n,int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
if(a[i]) cout<>n;
dfs(n,1);
}
递归实现组合型枚举（AcWing 93）
题目链接：递归实现组合型枚举
输出1~n中挑选m个数的所有组合方案。
使用深度优先搜索（DFS）
AC代码：
点击查看代码
# include
using namespace std;
const int N=30;
int a[N];
int n,m;
void dfs(int n,int m,int u,int k)
{
if(n-k+1+u=m)
{
for(int i=1;i<=n;i++)
if(a[i]) cout<>n>>m;
dfs(n,m,0,1);
}
递归实现排列型枚举（AcWing 94）
题目链接：递归实现排列型枚举
输出1~n的所有排列，可以利用DFS算法
AC代码：
点击查看代码
# include
using namespace std;
const int N=10;
int a[N];
bool st[N];
void dfs(int n,int u)
{
if(u>n)
{
for(int i=1;i<=n;i++)
cout<>n;
dfs(n,1);
}
费解的开关（AcWing 95）
题目链接：费解的开关
从第i行改变i-1行的状态，最后如果第n行仍存在0，说明该方法不可用，所以第一行的状态就决定了全局的状态，所以需要先枚举第一行的32种状态；
点击查看代码
# include
using namespace std;
const int N=7;
int p[N][N],a[N][N];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};
void turn(int a,int b)
{
for(int i=0;i<5;i++)
{
int x=a+dx[i];
int y=b+dy[i];
if(p[x][y]==0) p[x][y]=1;
else p[x][y]=0;
}
}
int main()
{
int n;
cin>>n;
while(n--)
{
for(int i=1;i<=5;i++)
{
string s;
cin>>s;
for(int j=1;j<=5;j++)
a[i][j]=s[j-1]-'0';
}
int res=7;
for(int k=0;k<32;k++)
{
int t=0;
bool flag=true;
memcpy(p,a,sizeof a);
for(int i=0;i<5;i++)
{
if(k>>i&1)
{
t++;
turn(1,i+1);
}
}
for(int i=2;i<=5;i++)
{
for(int j=1;j<=5;j++)
if(p[i-1][j]==0)
{
turn(i,j);
t++;
}
}
for(int i=1;i<=5;i++)
{
if(p[5][i]==0)
{
flag=false;
break;
}
}
if(flag&&t<=6)
res=min(t,res);
}
if(res>6) cout<<"-1"< 奇怪的汉诺塔（AcWing 96）
题目链接：奇怪的汉诺塔
每一次移动n个，都需要把第n个放到D上，说明此时前n-1个在B和C上，我的理解是把前k个放在B上，把k+1到n-1个放在C上，这样放到B上的相当于四个塔的汉诺塔，放到C上的相当于3个塔的汉诺塔，然后枚举k得到答案。
设了两个数组，a数组代表三个塔的汉诺塔移动的次数+1，p数组代表四个塔的汉诺塔的移动次数。
AC代码：
点击查看代码
# include
using namespace std;
int a[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
int p[13];
//前i-j个移动到B，p[i-j];
//把j个移动到C，a[j]-1;
//把n移动到D，1；
//把j个移动到D，a[j]-1;
//把i个移动到D，p[i-j]；
int main()
{
p[1]=1;
//计算p[i+1];
cout< 约数之和（AcWing 97）
题目链接：约数之和
还没学会，先占坑。
分形之城（AcWing 98）
题目链接：分形之城
不会，占坑。