heart1221 @ 2023-11-23 17:20:04
求助,我在代码中标记的两个部分有什么区别呢?
因为函数要求a,b,c中任意一个大于20的数都会被算成w(20,20,20)
,那我记忆只要把任意一个大于20的一行都记忆成f[21][21][21]
,结果反正都一样,等下一个大于20的数来就会直接走记忆化的数组,可是为什么会出现Wrong Ans呢,我不太明白,因为我感觉第一种写法也就是在存储记忆化的过程中,下标不太一致,但是结果是一直的,那我就直接让大于20的都用一个结果都用一个状态不也一样吗,不太明白
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const LL N = 30;
LL a, b, c;
LL f[N][N][N];
LL w(LL a, LL b, LL c)
{
// 应该直接return1,否则下标有可能是负的,记忆就会出现segment
if(a <= 0 || b <= 0 || c <= 0) return 1;
else if(f[a][b][c] != -1) return f[a][b][c];
else if(a > 20 || b > 20 || c > 20) f[a][b][c] = w(20, 20, 20);
else if(a < b && b < c)
f[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else
f[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);
return f[a][b][c];
}
int main()
{
memset(f, -1, sizeof f);
while(1)
{
cin >> a >> b >> c;
if(a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = ", a, b, c);
// 第一种写法
if(a>20) a=21;
if(b>20) b=21;
if(c>20) c=21;
printf("%lld\n",w(a,b,c));
// 第二种写法
if(a > 20 || b > 20 || c > 20) printf("%lld\n", w(21,21,21));
else printf("%lld\n", w(a,b,c));
}
return 0;
}
by 瑾阳2012 @ 2023-12-03 14:56:01
@heart1221
你试试这一组样例(用第二种):
30 −1 0
答案为1