当前位置: 代码迷 >> 综合 >> HDU-1331 Function Run Fun (记忆化搜索)
  详细解决方案

HDU-1331 Function Run Fun (记忆化搜索)

热度:56   发布时间:2023-12-15 03:43:43.0

这里写图片描述

这里写图片描述

最简单的记忆化搜索,题目有点问题,a, b, c中若既满足其中一个不大于0,又满足其中一个大于20,按前一种情况。

Code:

#include<bits/stdc++.h>
using namespace std;
int w[21][21][21];int dfs(int a, int b, int c) {if (a <= 0 || b <= 0 || c <= 0) return 1;if (~w[a][b][c]) return w[a][b][c]; if (a < b && b < c) return w[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);else return w[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);
}int main() {int a, b, c, ans;memset(w, -1, sizeof(w));while(~scanf("%d%d%d", &a, &b, &c)) {if (a == -1 && b == -1 && c == -1) break;if (a <= 0 || b <= 0 || c <= 0) ans = 1;else if (a > 20 || b > 20 || c > 20) ans = dfs(20, 20, 20);else ans = dfs(a, b, c);printf("w(%d, %d, %d) = %d\n", a, b, c, ans);}return 0;
}
  相关解决方案