P1464 Function
题目描述
对于一个递归函数 $w(a,b,c)$
- 如果 $a \le 0$ 或 $b \le 0$ 或 $c \le 0$ 就返回值$ 1$。
- 如果 $a>20$ 或 $b>20$ 或 $c>20$ 就返回 $w(20,20,20)$
- 如果 $a<b$ 并且 $b<c$ 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,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)$
这是个简单的递归函数，但实现起来可能会有些问题。当 $a,b,c$ 均为 $15$ 时，调用的次数将非常的多。你要想个办法才行。
注意：例如 $w(30,-1,0)$ 又满足条件 $1$ 又满足条件 $2$，请按照最上面的条件来算，答案为 $1$。
输入格式
会有若干行。
并以 $-1,-1,-1$ 结束。
输出格式
输出若干行，每一行格式：
w(a, b, c) = ans
注意空格。
样例 #1
样例输入 #1
样例输出 #1
1
2
| w(1, 1, 1) = 2
w(2, 2, 2) = 4
|
提示
数据规模与约定
保证输入的数在 $[-9223372036854775808,9223372036854775807]$ 之间，并且是整数。
保证不包括 $-1, -1, -1$ 的输入行数 $T$ 满足 $1 \leq T \leq 10 ^ 5$。
代码
解法一：递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<iostream>
using namespace std;
typedef long long ll;
ll dp[30][30][30];
int main(){
for(register int i=0;i<=22;++i){
for(register int j=0;j<=22;++j){
dp[0][i][j]=1;
dp[i][0][j]=1;
dp[i][j][0]=1;
}
}
for(register int i=1;i<=20;++i){
for(register int j=1;j<=20;++j){
for(register int k=1;k<=20;++k){
if(i<j&&j<k){
dp[i][j][k]=dp[i][j][k-1]+dp[i][j-1][k-1]-dp[i][j-1][k];
}
else{
dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k]+dp[i-1][j][k-1]-dp[i-1][j-1][k-1];
}
}
}
}
ll a,b,c;
while(cin>>a>>b>>c&&(a!=-1||b!=-1||c!=-1)){
if(a<=0||b<=0||c<=0){
printf("w(%lld, %lld, %lld) = 1\n",a,b,c);
}
else if(a>20||b>20||c>20){
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,dp[20][20][20]);
}
else{
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,dp[a][b][c]);
}
}
return 0;
}
|
解法二：递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <stdlib.h>
#define fi first
#define se second
#define LL long long
using namespace std;
typedef pair<int, int> PII;
const int N = 30;
const int INF = 0x3f3f3f3f;
int f[N][N][N];
void solve() {
for (int i = 0; i <= 20; i++) {
for (int j = 0; j <= 20; j++) {
for (int k = 0; k <= 20; k++) {
f[i][j][k] = 1;
}
}
}
for (int i = 1; i <= 20; i++) {
for (int j = 1; j <= 20; j++) {
for (int k = 1; k <= 20; k++) {
if (i < j && j < k) {
f[i][j][k] = f[i][j][k - 1] + f[i][j - 1][k - 1] - f[i][j - 1][k];
} else {
f[i][j][k] = f[i - 1][j][k] + f[i - 1][j - 1][k] + f[i - 1][j][k - 1] - f[i - 1][j - 1][k - 1];
}
}
}
}
LL a, b, c;
while (cin >> a >> b >> c) {
LL x, y, z;
x = a, y = b, z = c;
if (a == -1 && b == -1 && c == -1) return;
if (a <= 0 || b <= 0 || c <= 0) {
printf("w(%lld, %lld, %lld) = %lld\n", x, y, z, 1);
continue;
}
if (a > 20 || b > 20 || c > 20) {
a = 20, b = 20, c = 20;
}
printf("w(%lld, %lld, %lld) = %lld\n", x, y, z, f[a][b][c]);
}
}
int main(){
solve();
return 0;
}
|
解法三：记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int p[30][30][30];
int fun(int a,int b,int c){
if(a <= 0 || b <= 0 || c <= 0){
return 1;
}
if(a > 20 || b > 20 || c > 20){
return fun(20,20,20);
}
if(p[a][b][c]) return p[a][b][c];
if(a < b && b < c){
return p[a][b][c] = fun(a,b,c-1)+fun(a,b-1,c-1)-fun(a,b-1,c);
}
return p[a][b][c] = fun(a-1,b,c)+fun(a-1,b-1,c)+fun(a-1,b,c-1)-fun(a-1,b-1,c-1);
}
signed main(){
int a,b,c;
while(cin >> a >> b >> c && (a != -1 || b != -1 || c != -1)){
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,fun(a,b,c));
}
}
|
