标签：

题面 题解

说实话，， 其实我也不知道这题正解是啥
你看着数据范畴不像爆搜题
但是爆搜他就是可以过， 我也不知道为啥
奇葩

Code #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <map> using namespace std; int X, a[1005], cnt, q[1000005], num[1000005]; map<int, bool> mp; template < typename T > inline T read() { T x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * w; } int greedy() { int res = 0, sum = X; for(int i = cnt; i; i--) { res += sum / a[i]; sum -= sum / a[i] * a[i]; } return sum ? 0x3f3f3f3f : res; } int bfs() { int l = 1, r = 0; q[++r] = 0, num[r] = 0; while(l <= r && r <= 1000000) { for(int i = 1; i <= cnt; i++) { q[++r] = q[l] + 1, num[r] = num[l] > X ? num[l] - a[i] : num[l] + a[i]; if(num[r] == X) return q[r]; if(mp[num[r]] == 1) { r--; continue; } mp[num[r]] = 1; } l++; } return 0x3f3f3f3f; } int main() { X = read <int> (); while(scanf("%d", &a[++cnt]) != EOF); cnt--; sort(a + 1, a + cnt + 1); if(!X) puts("0"); else printf("%d\n", min(greedy(), bfs())); return 0; }

[题解] [JSOI2010] 找零钱的洁癖

标签：

原文地点：https://www.cnblogs.com/ztlztl/p/12258451.html