求助
  • 板块P1464 Function
  • 楼主heart1221
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/23 17:20
  • 上次更新2023/11/23 20:03:10
查看原帖
求助
1128514
heart1221楼主2023/11/23 17:20

求助,我在代码中标记的两个部分有什么区别呢? 因为函数要求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;
}


2023/11/23 17:20
加载中...