关于dp
查看原帖
关于dp
482610
Mortidesperatslav楼主2023/8/13 14:22

为什么这样写会 TLE,求助。

题目(懒得修 LaTeX\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";
	}
}
2023/8/13 14:22
加载中...