题目来源：洛谷P1118 数字三角形
暴力搜索
看到题目的第一眼想的就是直接搜，发现不少TLE，我还减了不少枝…
超时，只有20分，通过几个运行结果来看，写法应该对了，只是全都TLE而已
- ^在c++中不是幂运算，是异或（如果两个相应位为“异”（值不同），则该位结果为1，否则为0。
0^0=0; 0^1=1; 1^0=1; 1^1=0）。幂运算用pow(base,power)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,tri[13][13],ans[13]; bool flag=true;
void dfs(int);
int main()
{
int start;
cin>>n>>start; tri[n][1]=start;
dfs(n-1);
if(!flag) for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
void dfs(int level)
{
if(flag){
int lbound=pow(2,level-1),ubound=tri[level+1][1]-lbound;
for(int i=lbound;i<=ubound;i++){
if(!flag) continue;
tri[level][1]=i;
bool jump=false;
for(int j=1;j<=n-level;j++){
tri[level][j+1]=tri[level+1][j]-tri[level][j];
if(tri[level][j+1]<lbound) {jump=true; break;}
if(tri[level][j+1]==tri[level][j]) {jump=true; break;}
}
if(jump) continue;
for(int j=1;j<=n-level+1;j++){
cout<<tri[level][j]<<" ";
}
cout<<endl;
if(level==1){
int sum=0;
for(int i=1;i<=n;i++){
sum+=pow(2,tri[1][i]);
sum-=pow(2,i);
}
if(sum==0){
for(int i=1;i<=n;i++) ans[i]=tri[1][i];
flag=false;
}
}
if(level>1&&flag==true) dfs(level-1);
}
}
}
|
杨辉三角
以下为杨辉三角一维dfs，只有70分，还是需要剪枝
首先要搞清楚这个数字三角形究竟是什么吧。大家可以自己在草稿纸上写一下，假设n为一个比较小的数(比如，按样例，4)，设第一行的n个数分别为a,b,c,…(我这里是a,b,c,d)，然后模拟加一下，就会发现sum是……
如果n为4，那么sum是a+3b+3c+d。
如果n为5，那么sum是a+4b+6c+4d+e。
如果n为6，那么sum是a+5b+10c+10d+5e+f。
观察各项的系数，你发现了什么？
如果你有敏锐的数学眼光，你会发现，各项系数恰与杨辉三角有关！
那么我们就可以枚举每个a,b,c,…，逐一与sum比较，就可以得出答案了。~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
int yanghui[13][13],ans[13],n,sum; bool vis[13];
int compute();
void dfs(int);
int main()
{
cin>>n>>sum;
memset(vis,true,sizeof(vis));
yanghui[1][1]=1;yanghui[2][1]=1;yanghui[2][2]=1;
for(int i=3;i<=n;i++){
yanghui[i][1]=1;
for(int j=2;j<=i;j++)
yanghui[i][j]=yanghui[i-1][j-1]+yanghui[i-1][j];
}
dfs(1);
return 0;
}
int compute()
{
int temp=0;
for(int i=1;i<=n;i++) temp+=ans[i]*yanghui[n][i];
return temp;
}
void dfs(int pointer)
{
for(int i=1;i<=n;i++){
if(vis[i]){
ans[pointer]=i;
vis[i]=false;
if(pointer==n&&compute()==sum) {
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
break;
}
if(pointer<n) dfs(pointer+1);
ans[pointer]=0;
vis[i]=true;
}
}
}
|
二维DFS
上面方法的问题在于：只在所有位置都选完的时候才判定是否符合条件(sum=sum_to_find|(在这个程序中)sum=compute())，但是有很多情况下在我们没选完的时候就已经不符合条件了(sum>sum_to_find)。我们必须要排除这种情况，这样的话就必须在搜索的同时记录现在状态下合(sum)的大小，那么我们就需要写一个二维的dfs
~~实在太蠢了，把所有要判定的地方都加上&flag运行时间直接从1500ms提到了101ms ~~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
int yanghui[13][13],ans[13],n,sum_to_find; bool vis[13],flag=true;
int compute();
void dfs(int,int);
int main()
{
cin>>n>>sum_to_find;
memset(vis,true,sizeof(vis));
yanghui[1][1]=1;yanghui[2][1]=1;yanghui[2][2]=1;
for(int i=3;i<=n;i++){
yanghui[i][1]=1;
for(int j=2;j<=i;j++)
yanghui[i][j]=yanghui[i-1][j-1]+yanghui[i-1][j];
}
dfs(1,0);
return 0;
}
void dfs(int pointer,int sum)
{
if(flag){
for(int i=1;i<=n;i++){
if(vis[i]&&flag){
ans[pointer]=i;
vis[i]=false;
sum+=ans[pointer]*yanghui[n][pointer];
if(pointer==n&&sum==sum_to_find&&flag) {
for(int i=1;i<=n;i++) {cout<<ans[i]<<" "; flag=false;}
break;
}
if(pointer<n&&sum<sum_to_find&&flag) dfs(pointer+1,sum);
sum-=ans[pointer]*yanghui[n][pointer];
ans[pointer]=0;
vis[i]=true;
}
}}
}
|
