相关链接
题目传送门:http://codeforces.com/contest/788/problem/C
官方题解:http://codeforces.com/blog/entry/51312
解题报告
假设取$x$个物品的时候原问题有解,且第$i$个物品的编号为$b_i$
那么此时满足这个等式:$\sum\limits_{i=1}^{x}{a_{b_i}}=nx$
这个看起来既不满足单调性,又不能方便地$DP$
但如果我们把$n$给减到$a_i$里去,那么就是$\sum\limits_{i=1}^{x}{a_{b_i}}=0$
这个就好办了,直接搞一个$O(n^2)$的那个$BFS$
这个技巧应用较为广泛,还有一些升级版本
比如这个题:http://oi.cyo.ng/?p=3069
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 2009; const int M = 2000009; const int BAS = 1000; int n,m,tot,dis[N],head[N]; int nxt[M],to[M],_hash[M]; queue<int> que; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int main() { n = read(); m = read(); for (int i=1;i<=m;i++) _hash[++tot] = read() - n; sort(_hash+1, _hash+1+tot); tot = unique(_hash+1, _hash+1+tot) - _hash - 1; for (int i=1;i<=tot;i++) { dis[_hash[i] + BAS] = 1; que.push(_hash[i] + BAS); } while (!que.empty()) { int w = que.front(); que.pop(); for (int i=1,t;t=w+_hash[i],i<=tot;i++) { if (t < 0 || t > BAS*2 || dis[t]) continue; dis[t] = dis[w] + 1; que.push(t); } } cout<<(dis[BAS]?dis[BAS]:-1); return 0; }