ZROI#1005-蒲公英云

ZROI#1005

墨蓝 2023-06-02 12:52 121阅读 0赞

ZROI#1005

非常令人迷惑的一个题…
首先,我们发现,那个\(M\)并没有什么卵用.
于是我们直接不鸟它.
然后我们发现我们需要找一个最小的糖浆的集合\(S\).
使得下式成立:
\[\sum_{i\in S}{k_i*v_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:\)

#include <algorithm> #include <assert.h> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define int long long #define pb push_back 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 ; }