如题,已经很努力的调试了,但是调不出来,有没有大佬可以帮忙看看呐 QAQ
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 1e8;
const int N = 100;
const int M = 100;
struct node {
int u, last, step;
};
unordered_map <int, int> F;
unordered_map <int, unordered_map <int, int> > vis;
int limit;
int updt(int x, int y) {
if(!x) return x;
else return min(x, y);
}
vector <int> vec[N + 10];
int tot = 0;
void bfs() {
queue <node> que;
que.push((node){1, 0, 1});
vis[1][0] = 1;
while(!que.empty()) {
const node fr = que.front(); que.pop();
if(fr.step == limit) continue;
const int u = fr.u;
que.push((node){fr.u, fr.last + 1, fr.step + 1});
if(fr.last <= 1) continue;
ll v = 1ll * fr.u * 1ll * fr.last;
if(v > inf) continue;
if(!vis[v][fr.step + 1])
tot++,
vec[fr.step + 1].push_back(v),
vis[v][fr.step + 1] = 1,
// cout << v << ' ' << fr.step + 1 << endl,
que.push((node){(int)v, fr.last, fr.step + 1});
}
}
int n, m;
int a[N + 10], w[N + 10], mc;
int f[N + 10][N * 2 + 10];
void updmin(int &x, int y) {
x = min(x, y);
}
int qry(int x) {
if(x <= limit) return 1;
else {
for(int i = 1; i <= limit; i++) {
for(int k = 0; k < vec[i].size(); k++) {
int w = vec[i][k];
if(w > x) continue;
if(x - w + i <= limit) return 1;
for(int j = i; j + i <= limit; j++) {
int l = 0, r = vec[j].size() - 1, pos = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(vec[j][mid] + w <= limit) l = mid + 1, pos = mid;
else r = mid - 1;
}
if(pos > 0) {
int rest = w + vec[j][pos];
if(x - rest + i + j <= limit) return 1;
}
}
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> mc;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> w[i];
memset(f, 0x3f, sizeof(f));
f[0][mc] = 0;
int rest = mc;
for(int i = 0; i < n; i++) {
for(int j = a[i + 1]; j <= mc; j++) {
updmin(f[i + 1][j - a[i + 1]], f[i][j]);
updmin(f[i + 1][min(j - a[i + 1] + w[i + 1], mc)], f[i][j] + 1);
}
}
for(int i = 0; i <= n; i++)
for(int j = 0; j <= mc; j++)
limit = max(limit, i - f[i][j]);
bfs();
for(int i = 1; i <= limit; i++)
sort(vec[i].begin(), vec[i].end());
while(m--) {
int x;
cin >> x;
cout << qry(x) << '\n';
}
}