AOJ0070 Combination of Number Sequences

解法

---

書いていて気持ちが良くなるメモ化再帰。
書いていて気持ちが良い(再掲)

ソース

---

#include<iostream>
#include<algorithm>
using namespace std;
int dp[10][1<<10][331], n; //nの制約は自明だけど sはどれくら(ry ← 331か
int rec( int now, int used,int sum){
  if( sum < 0 ) return 0;
  if( now == n ) return sum == 0;
  if(~dp[now][used][sum]) return dp[now][used][sum];
  int ret = 0;
  for(int i = 0 ; i < 10 ; i++ ){
    if((used >> i) & 1)
      ret += rec( now + 1, used&~(1 << i), sum - i * (now + 1));
  }
  return dp[now][used][sum] = ret;
}
int main(){
  int s;
  while(cin >> n >> s){
    fill_n( **dp, 10 * (1 << 10) * 331, -1);
    cout << rec( 0, (1 << 10) - 1, s) << endl;
  }
}