首页 > 代码库 > UESTC 1634 去年春恨却来时，落花人独立，微雨燕双飞
UESTC 1634 去年春恨却来时，落花人独立，微雨燕双飞
题意：给你n个数（n<2000）q（q<10000）个询问s,求n个数是否能取任意个数相加得到s
题解：一开始以为是数论写半天。。。可以把这些数分类，分成a[1]类，每一类的数可以由最小的数加上t个a[1]得到，
初始得到的数只能是0，每个点到0的距离为无穷大，每次更新最短路,SPFA跑的更快一点
#include <bits/stdc++.h>#define maxn 100010using namespace std;int dis[maxn], n, a[maxn];void bfs(int fi){ memset(dis, 63, sizeof(dis)); dis[0] = 0; queue<int >q; q.push(fi); while(!q.empty()){ fi = q.front(); q.pop(); for(int i=1;i<n;i++){ if(dis[fi]+a[i]<dis[(fi+a[i])%a[0]]){ dis[(fi+a[i])%a[0]] = dis[fi]+a[i]; //dir[(fi+a[i])%a[0]] = 1; q.push((fi+a[i])%a[0]); } } }}int main(){ int m, q; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; bfs(0); cin>>q; while(q--){ cin>>m; cout<<((dis[(m)%a[0]]<=m)?"YES":"NO")<<endl; } return 0;}
UESTC 1634 去年春恨却来时，落花人独立，微雨燕双飞
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。