我先谔谔一波 /kk 我谔谔
看题第一眼：欸这不就是按题意递归嘛，，直接搞不就好了
3 min 后，重新看题
然后自己手玩了几个样例，噢，递归太多了，铁定会 T 啊......
然后，作为一个从没写过记忆化搜索的蒟蒻，苦苦思索了十几分钟。。。。。。
然后忽然想到可以用一个数组记录每一次的状态，然后如果递归到重复的数字直接返回记录的值，这就叫记忆化搜索！
我竟然就这样把记忆化搜索给 yy 出来了......
然后就是无尽的采坑。。。
首先，就是开了一个叫 \(\mathtt{mem}\) 的三维数组，然后每次递归就查询对应的位置，如果有值就返回，否则再按题目的意思一个一个去把 \(\mathtt{mem}\) 数组赋值。写出来大概就是这个样子：
long long w(long long a,long long b,long long c)
{
if(mem[a][b][c]!=0) return mem[a][b][c];
if(a<=0||b<=0||c<=0) return 1;
else if(a>20||b>20||c>20) mem[a][b][c]=w(20,20,20);
else if(a<b&&b<c) mem[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else mem[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);
}
然而又 WA 又 T 的，心酸。。。
然后突然发现数据范围： \([−9223372036854775808,9223372036854775807]\)
那递归开头就去判断如果下标是一个很大的负数咋办？？？岂不是会出现奇奇怪怪的错误？？？
所以，可以将函数里的第一行和第二行调换一下，这样就先去判断是否是负数了
long long w(long long a,long long b,long long c)
{
if(a<=0||b<=0||c<=0) return 1;
if(mem[a][b][c]!=0) return mem[a][b][c];
else if(a>20||b>20||c>20) mem[a][b][c]=w(20,20,20);
else if(a<b&&b<c) mem[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else mem[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);
}
然而又 WA 了！！！咋回事啊？？？
于是经过长达十几分钟的手玩数据，发现最后不会返回答案！！！所以在函数最后返回这个值就好了......
long long w(long long a,long long b,long long c)
{
if(a<=0||b<=0||c<=0) return 1;
else if(mem[a][b][c]!=0) return mem[a][b][c];
else if(a>20||b>20||c>20) mem[a][b][c]=w(20,20,20);
else if(a<b&&b<c) mem[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else mem[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 mem[a][b][c];
}
这下呢？？？20分！！！
然后又是十几分钟的手玩数据，突然发现 \(\mathtt{mem}\) 数组的值每次不会被清空。换而言之，在以后我们每次都在使用上次记忆的值。
既然如此，每次把 \(\mathtt{mem}\) 数组清零不久好了？？？
这个时候主函数就被改成了这样
int main()
{
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)&&(a!=-1)&&(b!=-1)&&(c!=-1))
printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
return 0;
}
还是不行！！！为啥？？？不难发现，若 \(a,b,c\) 的值过大，记忆数组存不下！！！
如何解决呢？考虑当 \(>20\) 时，并不会对 \(a,b,c\) 本身进行操作，换而言之，\(a=114514\) 和 \(a=21\) 本质是一样的！！！
int main()
{
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)&&(a!=-1)&&(b!=-1)&&(c!=-1))
{
memset(mem,0,sizeof(0));
printf("w(%d, %d, %d) = ",a,b,c);
//注意，下面的 a,b,c 要被修改，所以得先行输出
if(a>20) a=21;
if(b>20) b=21;
if(c>20) c=21;
printf("%d\n",w(a,b,c));
}
return 0;
}
还是过不了！！！我要被搞疯了
最后还是把错误 yy 了出来， while 里的判断条件会使得如果 \(a,b,c\) 有一个是负数（不是 \(-1\) ）就会结束......
最终 \(\mathtt{AC}\) 代码......
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
long long mem[101][101][101]={};
long long w(long long a,long long b,long long c)
{
if(a<=0||b<=0||c<=0) return 1;
else if(mem[a][b][c]!=0) return mem[a][b][c];
else if(a>20||b>20||c>20) mem[a][b][c]=w(20,20,20);
else if(a<b&&b<c) mem[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else mem[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 mem[a][b][c];
}
int main()
{
long long a,b,c;
while(scanf("%lld%lld%lld",&a,&b,&c)==3)
{
if((a==-1)&&(b==-1)&&(c==-1)) break;
memset(mem,0,sizeof(0));
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));
}
return 0;
}