悬关,wa#2和subtask的#1,#3
查看原帖
悬关,wa#2和subtask的#1,#3
854995
flyWang楼主2024/4/12 12:33
#include<bits/stdc++.h>
#define endl '\n'
#define int int64_t
#define ld long double
using namespace std;
int dx[] = { -1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };
const int NC = 2e3 + 10;
char ches[NC][NC];
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N], b[N], n, ans, m, k;
string s, sz;
bool cmp(string s1, string s2) {
    if (s1.size() > s2.size()) return true;
    if (s1.size() < s2.size()) return false;
    return s1 > s2;
}
void dfs(int u, int pre, int sum, int cnt) {
  //可行性剪枝,大于就走
    if (cmp(s.substr(pre, u - pre + 1), sz)) return;
    if (u == m) {
        if (sum + stoll(s.substr(pre, u - pre + 1)) == n) {
            ans = min(ans, cnt);
        }
        return;
    }
    dfs(u + 1, u + 1, sum + stoll(s.substr(pre, u - pre + 1)), cnt + 1);
    dfs(u + 1, pre, sum, cnt);
}
void solve() {
    cin >> s;
    cin >> n;
    string t = "";
   //这里去0对不对???
    for(int i = 0;i < s.size();++i){
        if(s[i] != '0') t += s[i];
    }
    s = t;
    if(s.empty()){
        cout << -1 << endl;
        return;
    }
    m = s.size();
    s = "!" + s;
    sz = to_string(n);
    ans = INT_MAX;
    dfs(1, 1, 0, 0);
    if(ans != INT_MAX)
        cout << ans << endl;
    else cout << -1 << endl;
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
2024/4/12 12:33
加载中...