Algoogle

Algorithm for Programming Contest

AOJ 2545 Lion

Category: AOJ Tag: implementation

Lion

問題概要


解法


入力の制限から全探索してもよさそうだとわかるので全て試して,
条件に合うもののうち合計が最大になる檻のなかのライオンの数を求める.

####


(2545.cpp) download
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>

#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back

using namespace std;

struct S{
    int l, r, s;
    S(int l, int r, int s):l(l),r(r),s(s){}
};

int n, x, m, atta;
vector<S> data;
int ans[8], ori[8];

void dfs(int cur){
    if(cur == n){
        rep(i,m){
            int l = data[i].l, r = data[i].r;
            int sum = 0;
            repi(j,l,r+1) sum += ori[j];
            if(sum != data[i].s) return;
        }
        int sum = 0;
        rep(i,n) sum += ori[i];
        if(sum > atta){
            rep(i,n) ans[i] = ori[i];
            atta = sum;
        }
        return;
    }
    rep(i,x+1){
        ori[cur] = i;
        dfs(cur+1);
    }
}

int main(){
    cin >> n >> x >> m;
    rep(_,m){
        int l, r, s;
        cin >> l >> r >> s;
        l--; r--;
        data.pb(S(l,r,s));
    }
    atta = -1;
    dfs(0);
    if(atta == -1) cout << atta << endl;
    else  rep(i,n) cout << ans[i] << (i==n-1? '\n': ' ');
}

Comments