[BOJ]16938号:キャンプ準備(C++)

10234 ワード
cpp algorithm baekjoon テキストリンク
質問リンク:白峻16938号です。

[質問へのアクセス]


nの数は大きくないので,重複しない組合せで解く.
回転コンビネーション時、問題数が2本を超える場合
  • 題の難易度の和はLに等しく、Rより小さいかまたは等しいか、
  • 最も難しい問題と最も容易な問題の難易度の違いがX以上の場合
    ansを増やせばいいです.
    • 問題の難易度の違いを求める方法で,降順に並べた後,組合せの中で最初に現れる問題と最後に現れる問題を選択し,それぞれ最も難しい問題,最も容易な問題を求めることができる.

    [ソースコード]

    #include <iostream>
#include <algorithm>

using namespace std;
int n,l,r,x,ans=0;
int arr[15];
bool visit[15];

bool cmp(int a, int b) {
    return a>b;
}

void solve(int index, int cnt, int sum) {
    if(cnt>=2) {
        int maxnum, minnum;
        for(int i=0 ; i<n ; i++) {
            if(visit[i] == true) {
                maxnum = arr[i];
                break;
            }
        }
        for(int i=n-1 ; i>=0 ; i--) {
            if(visit[i] == true) {
                minnum = arr[i];
                break;
            }
        }
        if(sum>=l && sum<=r && (maxnum-minnum)>=x) {
            ans++;
        }
    }
    for(int i=index ; i<n ; i++) {
        visit[i] = true;
        solve(i+1, cnt+1, sum+arr[i]);
        visit[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> l >> r >> x;
    for(int i=0 ; i<n ; i++) {
        int a;
        cin >> a;
        arr[i] = a;
    }
    
    sort(arr, arr+n, cmp);

    solve(0, 0, 0);
    

    cout << ans << "\n";

    return 0;
}
    [JAVA]制御文
    カスタムフックを使用した共有状態