ZROI#1005

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

[ZROI\#1005][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 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11571543.html

[ZROI_1005]: http://www.zhengruioi.com/problem/1005