## 2011年4月11日月曜日

### Being hooked on something makes you strong

I watched a TV drama entitled "aibou," which means buddy, co-worker or that kind of thing in Japanese, on this new year's day.
On the drama, a wife who had lost her son by a traffic accident, made explosive bombs and revenged on someone who killed her son.
On the drama, a detective, who solved the case, said "You think that an average house wife cannot make bombs, right? But one can do anything if s/he tries it all out."
And he continued, "She became really keen on studying about bomb. It made her proactive, outgoing and lively. Even though she stayed up late in the night -- 2 or 3 AM -- every day, she never looked sleepy. She looked cheerful every day."

あれ、何か。前置きが長くなった。
まー要約すると、最近仕事が忙しいことを言い訳にしてアルゴリズムの勉強をサボりがちだったけど、それは違うなと思いました。

そして、その方が活力的な生活が送れるはずだと信じています。

って、こんな精神論を書きたいわけじゃなかったのですが、

ちょっと文章が分かり難いですが、要は、
「mをn個以下に分割するパターンを求めよ。」
です。

これくらいの規模ならDFSとかで解けそうですが、入力サイズが大きくなると動的計画じゃないと厳しそうです。。
`int dp[16][16];void init() {   REP(i, 16)       dp[i][0] = 0, dp[0][i] = 1;   dp[0][0] = 1;   FOR (i, 1, 16) FOR (j, 1, 16) {       if (i-j >= 0)           dp[i][j] = dp[i][j-1] + dp[i-j][j];       else           dp[i][j] = dp[i][j-1];   }}int main() {   int t, n, m;   init();   scanf("%d", &t);   REP(i, t) {       scanf("%d %d", &n, &m);       printf("%d\n", dp[n][m]);   }   return 0;}`