You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
const int N = 30 ;
const int M = 1e4 + 10 ;
/*
2
3 5
答案：
4
最大不能表示的应该是：
四个不能表示的数是：
*/
int f [ M ] ;
int w [ N ] ;
int res ;
int gcd ( int a , int b ) {
if ( b = = 0 ) return a ;
return gcd ( b , a % b ) ;
}
int main ( ) {
int n ;
cin > > n ;
for ( int i = 1 ; i < = n ; i + + ) cin > > w [ i ] ;
sort ( w + 1 , w + 1 + n ) ;
int m1 = w [ 1 ] , m2 = w [ 2 ] ;
int M = m1 * m2 - m1 - m2 ;
int g = w [ 1 ] ;
for ( int i = 2 ; i < = n ; i + + ) g = gcd ( g , w [ i ] ) ;
if ( g > 1 ) {
cout < < " -1 " < < endl ;
return 0 ;
}
//完全背包一维写法
for ( int i = 1 ; i < = n ; i + + )
for ( int j = w [ i ] ; j < = M ; j + + )
f [ j ] = max ( f [ j ] , f [ j - w [ i ] ] + w [ i ] ) ;
for ( int i = 1 ; i < = M ; i + + )
if ( f [ i ] < i ) res + + ;
printf ( " %d \n " , res ) ;
return 0 ;
}
