AOJ2545 ライオン

解法

---

全探する。考えられる組み合わせをすべて挙げればいい感じにできる。
できるだけライオンを檻の中に多く入れたいので、あんな感じ(以下ソース参照)に檻に入れられる最大値からループを回す。

ソース

---

#include<iostream>
using namespace std;
 
int n, x, m, l[10], r[10], s[10];
int ret[6];
 
bool rec( int now, int sum){
  if(now == n){
 
    int sum[6] = {};
    for(int i = 0 ; i < n ; i++){
      sum[i + 1] = sum[i] + ret[i];
    }
    for(int i = 0 ; i < m ; i++ ){
      if(sum[r[i]] - sum[l[i] - 1] != s[i]) return false;
    }
    for(int i = 0 ; i < n ; i++ ){
      cout << (i  ? " " : "") << ret[i];
    }
    cout << endl;
    return true;
 
  }
  for(int i = x ; i >= 0 ; i--){
    ret[now] = i;
    if(rec( now + 1, sum - i)) return true;
  }
  return false;
}
 
int main(){
  cin >> n >> x >> m;
  for(int i = 0; i < m; i++){
    cin >> l[i] >> r[i] >> s[i];
  }
  if(!rec(0,m)) cout << "-1\n";
}