問題
http://topcoder.bgcoder.com/print.php?id=1669
サイコロが複数与えられる。
各サイコロは、いくつまでの目をもっているかあらかじめわかっている。
このとき、すべてのサイコロの目の出方の組み合わせは何通りあるか求める。
ただし、サイコロの区別はしない。
解き方
サイコロを、もつ目の数の昇順にソートする。
左から、１から始まりそれ以降の組み合わせをその数以上、としてｄｐで回せば重複なく答えが求められる。
メモ化が必要なので、現在のサイコロの場所と前のサイコロの目を状態としてもてば計算量は間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int n;
vector<int> sides;
long long dp[40][40];
class DiceGames {
public:
long long rec(int pos,int cnt){
if(pos==n)return 1;
if(dp[pos][cnt]!=-1)return dp[pos][cnt];
long long ret=0;
FORE(i,cnt,sides[pos]+1)ret+=rec(pos+1,i);
return dp[pos][cnt]=ret;
}
long long countFormations(vector<int> sides_) {
sides=sides_;
n=sides.size();
sort(all(sides));
memset(dp,-1,sizeof(dp));
return rec(0,1);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int n;
vector<int> sides;
long long dp[40][40];
class DiceGames {
public:
long long rec(int pos,int cnt){
if(pos==n)return 1;
if(dp[pos][cnt]!=-1)return dp[pos][cnt];
long long ret=0;
FORE(i,cnt,sides[pos]+1)ret+=rec(pos+1,i);
return dp[pos][cnt]=ret;
}
long long countFormations(vector<int> sides_) {
sides=sides_;
n=sides.size();
sort(all(sides));
memset(dp,-1,sizeof(dp));
return rec(0,1);
}
};