【第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;
}

cin int return 数组效率

0 人点赞