naoya_t@topcoder

SRM401 Div1 Easy: FIELDDiagrams

過去問, 練習 | 18:04 |

DP。単純な問題だが手間取っている。DPでいきなりコーディングは空中分解しがち。

#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class FIELDDiagrams {
public:
  int fo;
  vector<long long> memo;

  long long sub(int last,int fieldOrder){
    int ceil = min(last,fieldOrder);
    if (ceil == 0) { return 1;}

    int key=(ceil<<5)|fieldOrder;
    if (memo[key]>=0) return memo[key];
    long long count=1LL;
    for(int ai=ceil;ai>0;ai--){
      count += sub(ai,fieldOrder-1);
    }
    return memo[key] = count;
  }
  
  long long countDiagrams(int fieldOrder) {
    fo = fieldOrder;
    memo.resize(1024); fill(all(memo),-1);

    long long count = 0LL;
    for (int a1=fieldOrder;a1>0;a1--) {
      count += sub(a1, fieldOrder-1);
    }
    return count;
  }
};