ZROI#1005

ZROI#1005

非常令人迷惑的一个题...
首先,我们发现,那个(M)并没有什么卵用.
于是我们直接不鸟它.
然后我们发现我们需要找一个最小的糖浆的集合(S).
使得下式成立:

[sum_{iin S}{k_i*v_i}=N ]

其中(k_i)表示第(i)种糖浆选了几份,(v_i)表示糖浆浓度(cfrac{v_i}{M}).
但这个也并不好求.我们考虑转化.
如果我们把(v_i)变成(v_i-N),那么我们的目标就变成了使下式成立的最小的(S:)

[sum_{iin 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
" , f[base] ) ; 
    return 0 ;
}