The Balance

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5956 Accepted Submission(s): 2427

Problem Description

Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.

Input

The input consists of multiple test cases, and each case begins with a single positive integer N (1<=N<=100) on a line by itself indicating the number of weights you have. Followed by N integers Ai (1<=i<=N), indicating the quality of each weight where 1<=Ai<=100.

Output

For each input set, you should first print a line specifying the number of qualities which cannot be measured. Then print another line which consists all the irrealizable qualities if the number is not zero.

Sample Input

1 2 4

9 2 1

Sample Output

4 5

一条挺有意思的递推。

就是问给出n个重量为wi的砝码。

问你不能称出的重量有哪些。

bool dp[i][j] 表示前i个砝码，能否称出重量 j 。

初始化dp[0][0] = true ;

对于一个 dp[i-1][j] = true , 必然有 dp[i][j+a[i]] = true , dp[i][abs(j-a[i])] = true

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <stack>

#include <algorithm>

using namespace std;

#define root 1,n,1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define lr rt<<1

#define rr rt<<1|1

typedef long long LL;

typedef pair<int,int>pii;

#define X first

#define Y second

const int oo = 1e9+;

const double PI = acos(-1.0);

const double eps = 1e- ;

const int N = ;

const int mod = 1e9+;

bool dp[][N];

int n , m , a[N] , b[N] , tot ;

void init() {

    memset( dp , false ,sizeof dp );

    dp[][] = true ;

    for( int i =  ; i <= n ; ++i ){

        for( int j =  ; j <= tot ; ++j ){

            if( dp[i-][j] ) dp[i][j] = dp[i-][j];

            if( dp[i-][j] ){

                dp[i][j+a[i]] = true ; dp[i][abs(j-a[i])] = true ;

            }

        }

    //    for( int j = 0 ; j <= tot ; ++j ) cout << dp[i][j] << ' '; cout << endl ;

    }

}

void Run() {

    tot =  ;

    for( int i =  ; i <= n ; ++i )

        cin >> a[i] , tot += a[i];

    init(); int cnt =  ;

    for( int i =  ; i <= tot ; ++i ) if( !dp[n][i] ){

        b[cnt++] = i ;

    }

    cout << cnt << endl ;

    for( int i =  ; i < cnt ; ++i )

        cout << b[i] << (i+==cnt?"\n":" ");

}

int main()

{

//    freopen("in.txt","r",stdin);

    ios::sync_with_stdio(false);

    while( cin >> n ) Run();

}

秒客网

HDU 1709 The Balance( DP )

The Balance

相关文章