Zerojudge

zjd512_創造數字

連結:https://zerojudge.tw/ShowProblem?problemid=d512
題意:給你N個數字，問你任取幾個數字出來做加總，有多少不同數字。

這題乍看是DP，可是最大數字到2^31-1，這時可以用c++的STL，set來解決。set的實作是紅黑樹，尋找插入刪除複雜度皆O(logN)，這題方法就是依序和set裡的每一個數字加起來，如果還沒出現就插入set裡，注意這題要從後面做，因為set是從小排到大，從前面找會加到重複的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    set<LL>sb;
    set<LL>::iterator it;
    LL n,x;
    while(cin>>n){
        sb.clear();
        sb.insert(-1);//當結束點9
        sb.insert(0);
        for(int i=0;i<n;i++){
            cin>>x;
            it=sb.end();
            for(it--;it!=sb.begin();it--){
                if(sb.find(*it+x)==sb.end()){
                    sb.insert(*it+x);
                }
            }
        }
        cout<<sb.size()-2<<'\n';
    }
}

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

Recommended Posts