xk2013 @ 2024-02-07 21:33:02
源码（C++ 14 (GCC 9)）：
#include <cstdio>
long long int memory[25][25][25];
long long int w(long long int a, long long int b, long long int c);
int main(void)
{
long long int a, b, c;
while (a != -1 && b != -1 && c != -1)
{
scanf("%lld %lld %lld", &a, &b, &c);
if (a == -1 && b == -1 && c == -1)
{
break;
}
printf("w(%lld, %lld, %lld) = %lld", a, b, c, w(a, b, c));
}
return 0;
}
long long int w(long long int a, long long int b, long long c)
{
if (memory[a][b][c] != 0)
{
return memory[a][b][c];
}
else if (a <= 0 || b <= 0 || c <= 0)
{
return 1;
}
else if (a > 20 || b > 20 || c > 20)
{
memory[a][b][c] = w(20, 20, 20);
return memory[a][b][c];
}
else if (a < b && b < c)
{
if (memory[a][b][c - 1] == 0)
{
memory[a][b][c - 1] = w(a, b, c - 1);
}
if (memory[a][b - 1][c - 1] == 0)
{
memory[a][b - 1][c - 1] = w(a, b - 1, c - 1);
}
if (memory[a][b - 1][c] == 0)
{
memory[a][b - 1][c] = w(a, b - 1, c);
}
memory[a][b][c] = memory[a][b][c - 1] + memory[a][b - 1][c - 1] - memory[a][b - 1][c];
return memory[a][b][c];
}
else
{
if (memory[a - 1][b][c] == 0)
{
memory[a - 1][b][c] = w(a - 1, b, c);
}
if (memory[a - 1][b - 1][c] == 0)
{
memory[a - 1][b - 1][c] = w(a - 1, b - 1, c);
}
if (memory[a - 1][b][c - 1] == 0)
{
memory[a - 1][b][c - 1] = w(a - 1, b, c - 1);
}
if (memory[a - 1][b - 1][c - 1] == 0)
{
memory[a - 1][b - 1][c - 1] = w(a - 1, b - 1, c - 1);
}
memory[a][b][c] = memory[a - 1][b][c] + memory[a - 1][b - 1][c] + memory[a - 1][b][c - 1] - memory[a - 1][b - 1][c - 1];
return memory[a][b][c];
}
}我用了记忆化搜索，结果 RE，本地样例可过。
by xk2013 @ 2024-02-07 21:33:41
RID: 146495061
by xk2013 @ 2024-02-07 21:34:58
本贴不玄关，但玄……玄「YCOI」出题组名额！
by sybnb @ 2024-02-08 22:04:46
@xk2013 你最好不用三维数组，#1的a就是>200000
by sybnb @ 2024-02-08 22:07:36
只对于你的代码
by sybnb @ 2024-02-08 22:20:55
@xk2013 这是我的代码
#include<iostream>
#include<cstdio>
using namespace std;
long long ans[35][35][35];
long long a, b, c;
long long f(long long a, long long b, long long c){
if(a <= 0||b <= 0||c <= 0)
{
return 1;
}
else if(a > 20||b > 20||c > 20)
{
return ans[20][20][20] ? ans[20][20][20] : ans[20][20][20] = f(20,20,20);
}
else if(a < b&b < c)
{
return ans[a][b][c] ? ans[a][b][c] : ans[a][b][c] = f(a,b,c-1) + f(a,b-1,c-1) - f(a,b-1,c);
}
else
{
return ans[a][b][c] ? ans[a][b][c] : ans[a][b][c] = f(a-1,b,c) + f(a-1,b-1,c) + f(a-1,b,c-1) - f(a-1,b-1,c-1);
}
}
int main(){
scanf("%lld%lld%lld", &a, &b, &c);
while(a != -1||b != -1||c != -1)
{
printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, f(a,b,c));
scanf("%lld%lld%lld", &a, &b, &c);
}
return 0;
}by Abelxxyy @ 2024-02-25 09:24:26
@xk2013 记忆化搜索是先处理边界，在判断有没有算过，不是先判断，在处理边界。