プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
Quiz
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
AC Code
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3999614#1
分類
Bit DP
参考
http://ei1333.blogspot.com/2014/01/aoj0068-enclose-pins-with-rubber-band.html
解法
// i : 何個使ったか // j : すでに使った数字のフラグ // k : 作りたい値 ll dp[11][1024][331]; void reset(){ rep(i, 11){ rep(j, 1024){ rep(k, 331){ dp[i][j][k] = -1; // unused flag } } } } ll n; // cnt : 今まで使った回数 // f : 使った数字(フラグで管理) // sum : 作りたい値 ll rec(ll cnt, ll f, ll sum){ if(sum<0){ debug("can't make"); return 0; } if(cnt==n){ // もう選べない if(sum==0){ debug("select end", sum==0); return 1; }else{ debug("select end", sum==0); return 0; } } if(dp[cnt][f][sum]!=-1){ debug("already memo"); return dp[cnt][f][sum]; // メモがすでにある } ll ret = 0; rep(i, 10){ // 次の値としてiを選ぼうとする if(((f>>i)&1)==0){ ret += rec(cnt+1, f|(1<<i), sum - i * (cnt+1)); } } return dp[cnt][f][sum] = ret; } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll s; while(cin >> n >> s){ reset(); ll ans = rec(0, 0, s); p(ans); } return 0; }