DFS

跳台阶

一个楼梯共有 nn 级台阶，每次可以走一级或者两级，问从第 00 级台阶走到第 nn 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 nn。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

1≤n≤151≤n≤15

输入样例：

5

输出样例：

8

#include<bits/stdc++.h>
using namespace std;
int f(int n){
	if(n==1) return 1;
	if(n==2) return 2;
	return f(n-1)+f(n-2);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	cout<<f(n)<<endl;
	return 0;
} 

递归实现指数型枚举

从 1∼n1∼n 这 nn 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 nn。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤151≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
int st[N]; //用于记录是否选择当前数字，0表示待定，1表示选，2表示不选
void dfs(int x){
	if(x>n){
		for(int i=1; i<=n; i++){
			if(st[i]==1) cout<<i<<" "; 
		}
		cout<<endl;
		return ;
	}
	//不选当前的数字 
	st[x]=2;
	dfs(x+1);
	st[x]=0;
	
	//选当前的数字 
	st[x]=1;
	dfs(x+1);
	st[x]=0;
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	dfs(1);
	return 0;
} 

全排列问题

题目描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由 1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

**输入 **

3

输出

1    2    3
1    3    2
2    1    3
2    3    1
3    1    2
3    2    1

说明/提示

1≤n≤9。

#include<bits/stdc++.h>
using namespace std;
const int N=10; 
int n;
int arr[N];
bool st[N]; 
void dfs(int x){
	if(x>n){
		for(int i=1; i<=n; i++){
			cout<<setw(5)<<arr[i];
		}
		cout<<endl;
		return ;
	}
	for(int i=1; i<=n; i++){
		if(!st[i]){
			st[i]=true;
			arr[x]=i;
			dfs(x+1);
			//恢复 
			arr[x]=0;
			st[i]=false;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	dfs(1);
	return 0;
}

组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素（不分顺序且 r≤n），我们可以简单地将 n 个元素理解为自然数 1,2,…,n，从中任取 r 个数。

现要求你输出所有组合。

例如 n=5,r=3，所有组合为：

123,124,125,134,135,145,234,235,245,345。

输入格式

一行两个自然数 n,r(1<n<21,0≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 3 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;

输出占 3 个场宽的数 x。注意你需要头文件 iomanip。

输入输出样例

**输入 **

5 3 

**输出 **

1  2  3
1  2  4
1  2  5
1  3  4
1  3  5
1  4  5
2  3  4
2  3  5
2  4  5
3  4  5

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n, k;
int arr[N];
void dfs(int x, int start){
	if(x>k){
		for(int i=1; i<=k; i++){
			cout<<setw(3)<<arr[i];
		}
		cout<<endl;
		return;
	}
	
	for(int i=start; i<=n; i++){
		arr[x]=i;
		dfs(x+1,i+1);
		arr[x]=0;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	dfs(1, 1);
	return 0;
}

选数

题目描述

已知 n 个整数 x1,x2,⋯,x**n，以及 1 个整数 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,⋯,x**n（1≤x**i≤5×106）。

输出格式

输出一个整数，表示种类数。

输入输出样例

输入 #1复制

4 3
3 7 12 19

输出 #1复制

1

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n, k;
int arr[N];
int cs[N];
int res=0;
bool isPrime(int sum){
	for(int i=2; i<=sum/i; i++){
		if(sum%i==0) return false;
	}
	return true;
}

void dfs(int x, int start, int sum){
	if(x>k){
		if(isPrime(sum)) res++;
		return;
	}
	
	for(int i=start; i<=n; i++){
		arr[x]=cs[i];
		sum+=arr[x];
		dfs(x+1, i+1, sum);
		sum-=arr[x];
		arr[x]=0;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>cs[i];
	}
	dfs(1, 1, 0);
	cout<<res<<endl;
	return 0;
} 

烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 10 种配料的所有搭配方案。

输入格式

一个正整数 n，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束，10 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 0。

输入输出样例

输入 #1复制

11

输出 #1复制

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int n;
int res;
int arr[N];
int cs[10000][N]; //这里的范围要开的大一点
void dfs(int x, int sum){
	if(sum>n) return; 
	if(x>10){
		if(sum==n){
			res++;
			for(int i=1; i<=10; i++){
				cs[res][i]=arr[i];
			} 
		}

		return;
	}
	for(int i=1; i<=3; i++){
		arr[x]=i;
		sum+=arr[x];
		dfs(x+1, sum);
		sum-=arr[x];
		arr[x]=0;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	dfs(1, 0);
	cout<<res<<endl;
	for(int i=1; i<=res; i++){
		for(int j=1; j<=10; j++){
			cout<<cs[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
} 

火星人

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 1,2,3,⋯。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 1,2,3,4 和 5，当它们按正常顺序排列时，形成了 5 位数 12345，当你交换无名指和小指的位置时，会形成 5 位数 12354，当你把五个手指的顺序完全颠倒时，会形成 54321，在所有能够形成的 120 个 5 位数中，12345 最小，它表示 1；12354 第二小，它表示 2；54321 最大，它表示 120。下表展示了只有 3 根手指时能够形成的 6 个 3 位数和它们代表的数字：

三进制数	代表的数字
123	1
132	2
213	3
231	4
312	5
321	6

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数 N，表示火星人手指的数目（1≤N≤10000）。
第二行是一个正整数 M，表示要加上去的小整数（1≤M≤100）。
下一行是 1 到 N 这 N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

N 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

输入输出样例

输入 #1复制

5
3
1 2 3 4 5

输出 #1复制

1 2 4 5 3

说明/提示

对于 30% 的数据，N≤15。

对于 60% 的数据，N≤50。

对于 100% 的数据，N≤10000。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n, m;
bool st[N], return0;
int res=0;
int arr[N];
int mars[N];
void dfs(int x){
	if(return0) return;
	if(x>n){
		res++;
		if(res==m+1){
			for(int i=1; i<=n; i++){
				cout<<arr[i]<<" ";
			}
			return0=true;
		}
		return;
	}
	for(int i=1; i<=n; i++){
		if(res==0){
			i=mars[x];
		}
		if(!st[i]){
			st[i]=true;
			arr[x]=i;
			dfs(x+1);
			arr[x]=0;
			st[i]=false;
		}
	}
	
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		cin>>mars[i];
	}
	dfs(1);
	return 0;
}

火柴棒等式

题目描述

给你 n 根火柴棍，你可以拼出多少个形如 A+B=C 的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 0）。用火柴棍拼数字 0∼9 的拼法如图所示：

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果 A=B，则 A+B=C 与 B+A=C 视为不同的等式（A,B,C≥0）；
3. n 根火柴棍必须全部用上。

输入格式

一个整数 n(1≤n≤24)。

输出格式

一个整数，能拼成的不同等式的数目。

输入输出样例

输入 #1复制

14

输出 #1复制

2

输入 #2复制

18

输出 #2复制

9

说明/提示

【输入输出样例 1 解释】

2 个等式为 0+1=1 和 1+0=1。

【输入输出样例 2 解释】

9 个等式为

0+4=4、0+11=11、1+10=11、2+2

=4、2+7=9、4+0=4、7+2=9、10+1=11、11+0=11。

#include<bits/stdc++.h>
using namespace std;
int n;
int res;
int arr[4];
int num[10001]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void dfs(int x, int sum){
	if(sum>n) return;
	if(x>3){
		if(arr[1]+arr[2]==arr[3] && sum==n){
			res++;
		}
		return; 
	}
	for(int i=0; i<=1000; i++){ //这里数字不能开太大
		arr[x]=i;
		sum+=num[i];
		dfs(x+1, sum);
		sum-=num[i];
		arr[x]=0;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	n=n-4;
	for(int i=10; i<=1000; i++){
		num[i]=num[i/10]+num[i%10];
	}
	dfs(1, 0);
	cout<<res<<endl;
	return 0;
} 

PERKET

题目描述

Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。

众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。

输入格式

第一行一个整数 n，表示可供选用的食材种类数。

接下来 n 行，每行 2 个整数 s**i 和 b**i，表示第 i 种食材的酸度和苦度。

输出格式

一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

输入输出样例

输入 #1复制

1
3 10

输出 #1复制

7

输入 #2复制

2
3 8
5 8

输出 #2复制

1

输入 #3复制

4
1 7
2 6
3 8
4 9

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int n;
int acid[N], bitter[N];//酸度之积，苦度之和 
int arr[N];
int res=1e9;
int st[N];//0表示待定，1表示选，2表示不选 
void dfs(int x){
	bool has_tl=false;
	if(x>n){
			int mul=1, sum=0;
		for(int i=1; i<=n; i++){
			if(st[i]==1){
				has_tl=true;
				mul=mul*acid[i];
				sum=sum+bitter[i];
			}
		}
		if(has_tl==true){
			res=min(res, abs(mul-sum));
		}
		return ;
	}
	//不选
	st[x]=2;
	dfs(x+1);
	st[x]=0;
	
	//选
	st[x]=1;
	dfs(x+1);
	st[x]=0; 
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1; i<=n;i++){
		cin>>acid[i]>>bitter[i];
	}
	dfs(1);
	cout<<res<<endl;
	return 0;
} 

奇怪的电梯

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1≤i≤N）上有一个数字 K**i（0≤K**i≤N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： 3,3,1,2,5 代表了 K**i（K1=3，K2=3，……），从 1 楼开始。在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 −2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 N,A,B（1≤N≤200，1≤A,B≤N）。

第二行为 N 个用空格隔开的非负整数，表示 K**i。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

输入输出样例

输入 #1复制

5 1 5
3 3 1 2 5

输出 #1复制

3

说明/提示

对于 100% 的数据，1≤N≤200，1≤A,B≤N，0≤K**i≤N。

本题共 16 个测试点，前 15 个每个测试点 6 分，最后一个测试点 10 分。

//dfs有几个点会超时，只能用别的算法拿满分
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n, a, b;
int K[N];
bool st[N];
int res=1e9;
void dfs(int x, int sum){
	if(sum>=res) return;
	if(x<0 || x>n) return;
	if(x==b){
		res=min(res, sum);
		return;
	}

	//选上
	if(x+K[x]<=n && !st[x+K[x]]){
		st[x+K[x]]=true;
		dfs(x+K[x], sum+1);
		st[x+K[x]]=false;
	} 
	//选下
	if(x-K[x]>0 && !st[x-K[x]]){
		st[x-K[x]]=true;
		dfs(x-K[x], sum+1);
		st[x-K[x]]=false;
	} 
	
}
int main(){

	scanf("%d%d%d",&n,&a,&b);
	for(int i=1; i<=n; i++){
		scanf("%d", &K[i]);
	}
	dfs(a, 0);
	if(res==1e9){
		printf("-1");
	}else{
		printf("%d",res);
	}
	return 0;
}

入门

题目描述

不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。

由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。

注意：瓷砖可以重复走过，但不能重复计数。

输入格式

第一行两个正整数 W 和 H，分别表示小路的宽度和长度。

以下 H 行为一个 H×W 的字符矩阵。每一个字符代表一块瓷砖。其中，. 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。

输出格式

输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。

输入输出样例

输入 #1复制

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

输出 #1复制

59

//'.'和'#'别看反了
#include<bits/stdc++.h>
using namespace std;
const int N=25;
char g[N][N];
bool st[N][N];
int n, m;//n行m列
int res=0;
int dx[]={0, 1, 0, -1};
int dy[]={1, 0, -1, 0};
void dfs(int x, int y){
	int a, b;
	for(int i=0; i<4; i++){
		a=x+dx[i];
		b=y+dy[i];
		if(a<0 || a>=n || b<0 || b>=m || st[a][b] || g[a][b]!='.') continue;
		res++;
		st[a][b]=true;
		dfs(a, b);
	}
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=0; i<n; i++){
		scanf("%s", g[i]);
	} 
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(g[i][j]=='@'){
				res++;
				st[i][j]=true;
				dfs(i, j);
			}
		}
	} 
	printf("%d", res); 
	return 0;
} 

Lake Counting S

题意翻译

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 1 行：两个空格隔开的整数：N 和 M。

第 2 行到第 N+1 行：每行 M 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

输入输出样例

输入 #1复制

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出 #1复制

3

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n, m;
int res;
char g[N][N];
bool st[N][N];
int dx[]={0, 1, -1, -1, 1, 0, 1, -1};
int dy[]={1, 1, 1, 0, 0, -1, -1, -1};
void dfs(int x, int y){
	for(int i=0; i<8; i++){
		int a=x+dx[i], b=y+dy[i];
		if(a<0 || a>=n || b<0 || b>=m || st[a][b] || g[a][b]!='W') continue;//这里是st[a][b]，不是!st[a][b]不要一直写错了
		st[a][b]=true;
		dfs(a, b);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++){
		scanf("%s",g[i]);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(g[i][j]=='W'&& !st[i][j]){
				st[i][j]=true;
				dfs(i, j);
				res++;
			}
		}
	}
	printf("%d",res);
	return 0;
} 

棋盘问题

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 kk 个棋子的所有可行的摆放方案数目 CC。

输入格式

输入含有多组测试数据。

每组数据的第一行是两个正整数 n,kn,k，用一个空格隔开，表示了将在一个 n∗nn∗n 的矩阵内描述棋盘，以及摆放棋子的数目。当为-1 -1时表示输入结束。

随后的 nn 行描述了棋盘的形状：每行有 nn 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目 CC （数据保证 C<231C<231）。

数据范围

n≤8,k≤nn≤8,k≤n

输入样例：

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

输出样例：

2
1

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n, k;
bool st[N];//代表多少列有没有被选过
int res;
char g[N][N];
void dfs(int x, int cnt){
	if(cnt==k){
		res++;
		return;
	}
	
	if(x>=n) return;//这里一定不能写在前面，因为访问下一行时，需先判断旗子个数 
	
	for(int i=0; i<n; i++){
		if(!st[i] && g[x][i]=='#'){
			st[i]=true;
			dfs(x+1, cnt+1);
			st[i]=false;
		}
	}
	dfs(x+1, cnt);
}
int main(){
	scanf("%d%d", &n, &k);
	while(n!=-1 && k!=-1){
		for(int i=0; i<n; i++){
			scanf("%s", g[i]);
		}
		
		dfs(0, 0);
		printf("%d\n", res);
		res=0;
		scanf("%d%d", &n, &k);
	}
	return 0;
} 

数的划分

题目描述

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;
1,5,1;
5,1,1.

问有多少种不同的分法。

输入格式

n,k （6<n≤200，2≤k≤6）

输出格式

1 个整数，即不同的分法。

输入输出样例

输入 #1复制

7 3

输出 #1复制

4

说明/提示

四种分法为：
1,1,5;
1,2,4;
1,3,3;
2,2,3.

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n, k;
int res;
int arr[N];
void dfs(int x, int start, int sum){
	if(sum>n) return;
	if(x>k){
		if(sum==n) res++;
		return;
	}
	for(int i=start; sum+(k-x+1)*i<=n; i++){ //在这里剪枝
		arr[x]=i;
		dfs(x+1, i, sum+i);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	dfs(1, 1, 0);
	cout<<res<<endl;
	return 0;
} 

单词接龙

题目背景

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。

本题为搜索题，本题不接受 hack 数据。关于此类题目的详细内容

NOIP2000 提高组 T3

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

输入输出样例

输入 #1复制

5
at
touch
cheat
choose
tact
a

输出 #1复制

23

说明/提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int g[N][N];
int n;
char start;
string wrods[N][N];
int res;
int used[N];
void dfs(string dragon, int x){
	res=max(res, (int)dragon.size());
	used[x]++;
	for(int i=0; i<n; i++){
		if(g[x][i]!=0 && used[i]<=2){ 
			used[i]++;
			dfs(dragon+words[i].substr(g[x][i]), i)； 
			used[i]--;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>words[i];
	}
	cin>>start;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			string a=words[i], b=words[j];
			for(int k=1; k<min(a.size(), b.size()); k++){
				if(a.substr(a.size()-k,k)==b.substr(0,k)){
					g[i][j]=k;
					break;
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		if(words[i][0]==start){
			dfs(words[i], i);
		}
	}
	cout<<res<<endl;
	return 0;
}