【第65题】剪枝没学精TLE了，[USACO06FEB] Backward Digit Sums G/S
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1118
- 参考题解：https://www.luogu.com.cn/problem/solution/P1118
- 标签：
搜索、剪枝、回溯
题解
- 小码匠思路
- 我万万没想到将数组放在函数的传入参数中会导致严重的后果，正如70分代码所示，将一堆数组放在参数里导致了两个点TLE，至此我学会了将数组放在外面也可以降低时间
- 后面其实判断is完全可以和s > p同时进行，反正满足哪一个都要退出，放在后面还会平白增加计算量
- 看见这样的题无论是谁都会蹦出一个词吧【没错就是那个词——杨辉三角】
- 然后我们就可以深搜找符合条件的排列，顺序找可以保证字典序最小
- 最后是老节目:《模仿欧阳锋修炼九阴真经》又名《花式解锁失败如TLE，WA……》
- 官方题解
- 题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P1118
代码：70分（3case：TLE）
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
void dfs(int t, int s, int p, int n, vector<int> &v, vector<bool> &b, vector<vector<int>> Pas_tri, bool &is) {
if (s > p) {
return;
}
if (t > n) {
if (s == p && is) {
for (int i = 1; i <= n; i) {
cout << v[i] << " " ;
}
is = false;
}
return;
}
for (int i = 1; i <= n; i) {
if (!b[i]) {
b[i] = true;
v[t] = i;
dfs(t 1, s i * Pas_tri[n][t], p, n, v, b, Pas_tri, is);
b[i] = false;
}
}
}
void best_coder() {
int n, p;
cin >> n >> p;
vector<int> v(n 3);
vector<bool> b(n 3);
vector<vector<int>> Pas_tri(n 3, vector<int>(n 3));
Pas_tri[1][1] = 1;
for (int i = 2; i <= n; i){
for (int j = 1; j <= i; j) {
Pas_tri[i][j] = Pas_tri[i - 1][j] Pas_tri[i - 1][j - 1];
}
}
bool is = true;
dfs(1, 0, p, n, v, b, Pas_tri, is);
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
代码：90分（1case：TLE）
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
int v[20];
bool b[20];
int Pas_tri[20][20];
int p, n;
bool is = true;
void dfs(int t, int s) {
if (s > p) {
return;
}
if (t > n) {
if (s == p && is) {
for (int i = 1; i <= n; i) {
cout << v[i] << " " ;
}
is = false;
}
return;
}
for (int i = 1; i <= n; i) {
if (!b[i]) {
b[i] = true;
v[t] = i;
dfs(t 1, s i * Pas_tri[n][t]);
b[i] = false;
}
}
}
void best_coder() {
cin >> n >> p;
Pas_tri[1][1] = 1;
for (int i = 2; i <= n; i){
for (int j = 1; j <= i; j) {
Pas_tri[i][j] = Pas_tri[i - 1][j] Pas_tri[i - 1][j - 1];
}
}
dfs(1,0);
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
AC
注意
代码语言：javascript复制 if (s > p || !is) {
然后就AC
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
int v[20];
bool b[20];
int Pas_tri[20][20];
int p, n;
bool is = true;
void dfs(int t, int s) {
if (s > p || !is) {
return;
}
if (t > n) {
if (s == p && is) {
for (int i = 1; i <= n; i) {
cout << v[i] << " " ;
}
is = false;
}
return;
}
for (int i = 1; i <= n; i) {
if (!b[i]) {
b[i] = true;
v[t] = i;
dfs(t 1, s i * Pas_tri[n][t]);
b[i] = false;
}
}
}
void best_coder() {
cin >> n >> p;
Pas_tri[1][1] = 1;
for (int i = 2; i <= n; i){
for (int j = 1; j <= i; j) {
Pas_tri[i][j] = Pas_tri[i - 1][j] Pas_tri[i - 1][j - 1];
}
}
dfs(1,0);
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
