为什么这样写会 TLE,求助。
题目(懒得修 LATEX)
小Y去Lhc Market购物,不过这个Market有个不成文的规定,就是买东西不找零。比如说,《算法导论》要68元,你付了100元,他会收下,但不会找你32元,于是你就用100元买了68元的东西,亏大了。小Y身边只有n张纸币,每张纸币有一个正整数面额p,Market里有k种商品,每种商品都有一个正整数单价t。小Y现在想知道,用他的纸币能恰好凑出哪些商品的价格。例如:5 1 4 8 9能凑出17=8+9, 6=1+5, 10=1+9等,但不能凑出2,3等。
#include <bits/stdc++.h>
using namespace std;
map<long long,bool>f;
int n,a[10005],t;
queue<int>tmpq;
queue<int>q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
q.push(0);
f[0]=1;
for(int i=1;i<=n;i++){
int p,sum=q.size();
while(sum>0){
p=q.front();
sum--;
tmpq.push(p);
q.pop();
f[p+a[i]]=1;
q.push(p+a[i]);
}
while(!tmpq.empty()){
q.push(tmpq.front());
tmpq.pop();
}
}
cin>>t;
for(int i=1;i<=t;i++){
int x;
cin>>x;
if(f[x]==1)cout<<"possible\n";
else cout<<"impossible\n";
}
}