非常令人迷惑的一个题…
首先,我们发现,那个$M$并没有什么卵用.
于是我们直接不鸟它.
然后我们发现我们需要找一个最小的糖浆的集合$S$.
使得下式成立:
$$\sum_{i\in S}{k_iv_i}=N$$
其中$k_i$表示第$i$种糖浆选了几份,$v_i$表示糖浆浓度$\cfrac{v_i}{M}$.
但这个也并不好求.我们考虑转化.
如果我们把$v_i$变成$v_i-N$,那么我们的目标就变成了使下式成立的最小的$S:$
$$\sum_{i\in S}{k_i(v_i-N)}=0$$
这样就好做很多.
我们发现这其实相当于一个完全背包$:$
要求恰好装满一个容量为$0$的背包,每个物品有正有负且可取无限次的最小物品个数.
考虑直接$DP$.
令$f_i$表示恰好装满一个容量为$i$的背包,每个物品有正有负且可取无限次的最小物品个数.
有转移:
$f_i=min(f_i,f_{i-v_i}+1)$(正向,滚动数组基操)
需要注意的是,如果$v_i$小于$0$的话,需要从大的转移过来.否则需要从小的转移过来.
为了避免出现负下标,我们可以取一个基数$base$,每次把下标加上这个$base$,就可以避免负下标的出现.
$Code:$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int base = 25e4 ;
const int N = 1e7 + 100 ;
int n , m , k , v[N] , f[N] ;
signed main (int argc , char * argv[]) {
k = rint () ; n = rint () ; m = rint () ; MEM ( f , 0x7f ) ;
rep ( i , 1 , k ) { v[i] = rint () ; v[i] -= n ; f[v[i]+base] = 1 ; }
sort ( v + 1 , v + k + 1 ) ; k = unique ( v + 1 , v + k + 1 ) - v - 1 ;
rep ( i , 1 , k ) {
rep ( j , - base , base )
if ( j + base - v[i] < 0 ) continue ;
else f[j+base] = min ( f[j+base] , f[j+base-v[i]] + 1 ) ;
per ( j , base , - base )
if ( j + base - v[i] < 0 ) continue ;
else f[j+base] = min ( f[j+base] , f[j+base-v[i]] + 1 ) ;
}
if ( f[base] >= 0x7f7f7f7f ) puts ("-1") ;
else printf ("%lld\n" , f[base] ) ;
return 0 ;
}