POJ3413 - RPG

http://poj.org/problem?id=3413

POJから。某所で解けなかった問題を今更実装。

問題内容：
入力
RPGのクエストのクリアに必要な経験値A、十分な経験値Bと経験値S、初期状態の経験値D

制約
クエストは各1回選択できる。
クエスト1つが終わると成功失敗にかかわらず経験値を得る。
クエストの成功確率はクエスト選択時の経験値をEXPとして以下の通りに定められる。
・0 (EXP<=A)
・1 (EXP>=B)
・(EXP-A)/(B-A) (それ以外)
クエストの数は10以下、入力の経験値は全て1000以下

出力
全クエストを終了時最も成功確率が高くなる場合の成功確率とクエストの順番

解法
全探索
next_permutationして全通り試してみただけ
if(tmpprob>=maxprob)をif(tmpprob>maxprob)
にするとmaxprob=0の時に順番の出力が不正になりWA

およそ800～900ms要しておりやはりO(n*n!)は辛いと感じる一品

（にしても遅いような気がする）

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
using namespace std;
 
////////////////////////

double calc(int a,int b,int d){
  if(d<=a)return 0.0;
  else if(d>=b)return 1.0;
  else return (double)(d-a)/(b-a);
}

int main(){
  int n,d;
  int a[10],b[10],s[10];
  cin >> n >> d;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i] >> s[i];
  }
  vector<int> res(n),tmp(n);
  double maxprob=0.0;
  double tmpprob;
  int tmpexp;
  REP(i,n)tmp[i]=i;
  do{
    tmpprob = 1.0;
    tmpexp = d;
    for(int i=0;i<n;i++){
      tmpprob *= calc(a[tmp[i]],b[tmp[i]],tmpexp);
      tmpexp += s[tmp[i]];
    }
    if(tmpprob>=maxprob){
      maxprob = tmpprob;
      res = tmp;
    }
  }while(next_permutation(tmp.begin(),tmp.end()));
  cout << fixed << setprecision(3);
  cout << maxprob << endl;
  for(int i=0;i<n;i++){
    cout << res[i]+1 << " ";
  }cout << endl;
  return 0;
}