UVa

UVa00562 Dividing coins (Zerojudge d390)

連結1:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=503
連結2:https://zerojudge.tw/ShowProblem?problemid=d390
這題題意是要問所給出的m個幣值，分兩推的最小差距。

做法:先背包dp，再從可能的方法找出答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N=50005;

int main(){
    int n,m,x,sum,ans;
    bool dp[N];
    cin>>n;
    while(n--){
        memset(dp,0,sizeof(dp));
        sum=0;
        cin>>m;
        while(m--){
            cin>>x;
            sum+=x;
            for(int j=sum;j-x>=0;j--){
                if(!(j-x)||dp[j-x]){
                    dp[j]=1;
                }
            }
        }
        ans=sum;
        for(int i=1;i<=sum/2;i++){
            if(dp[i]){
                ans=sum-2*i;
            }
        }
        cout<<ans<<'\n';
    }
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts