1579 Function Run Fun

1579 Function Run Fun


たらいまわし関数。
友人が卒論でベンチマークとして竹内関数を使っていたとき初めて知ったたらいまわし関数。

普通に実装しちゃったら何時間もかかるよって問題文に書いてあるたらいまわし関数。

これは昔3036 Honeycomb Walkでやったメモ化というのが使えそうだ！と思ったけど書き方忘れてたからPKUで昔提出した3036を確認。

で、書いたら通った。メモ化したいときに見よう。

#include<cstdio>
#include<cstring>

using namespace std;

int memo[21][21][21];

int w(int a, int b, int c) {
    if (a >= 0 && a <= 20 && b >= 0 && b <= 20 && c >= 0 && c <= 20 && memo[a][b][c] != 0) {
	return memo[a][b][c];
    } else if (a <= 0 || b <= 0 || c <= 0) {
	return 1;
    } else if (a > 20 || b > 20 || c > 20) {
	return memo[20][20][20] = w(20, 20, 20);
    } else if (a < b && b < c) {
	return memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
    } else {
	return memo[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
    }
}

int main() {
    int a, b, c;
    memset(memo, 0, sizeof(memo));
    while (scanf("%d %d %d", &a, &b, &c), !(a == -1 && b == -1 && c == -1)) {
	printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    }
}