70pts TLE on #2 大佬帮忙优化一下暴搜
查看原帖
70pts TLE on #2 大佬帮忙优化一下暴搜
1350908
gjrBJ楼主2024/11/30 10:58

BaoLi函数只能通过#1#2是不是要用记忆化?大佬帮忙回复                \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 玄关QwQQwQ

#include <bits/stdc++.h>
using namespace std;
int t, n, ans, p[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void BaoLi(int n, int s) {
    if (n <= 0) {
        if (n == 0 && s != 0) ans = min(ans, s);
        return ;
    }
    for (int i = 0; i <= 9; i++) {
        if (s == 0 && i == 0) continue;
        BaoLi(n - p[i], s * 10 + i);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        if (n <= 50) {//暴搜
            ans = 1000000000;
            BaoLi(n, 0);
            cout << (ans == 1000000000 ? -1 : ans) << endl;
            continue;
        }
        //下面是特殊性质A, B
        if (n % 7 == 1) cout << "10";
        for (int i = 0; i < n / 7 - n % 7; i++) {
            cout << "8";
        }
        cout << endl;
    }
    return 0;
}
2024/11/30 10:58
加载中...