# 165 条题解

• @ 2016-05-27 22:11:26

总结一下：
1.记忆化搜索 或是 打表。。
2.严格按照题目叙述的优先级来写判断语句
3.仔细观察输出，注意空格

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 21;
int w[N][N][N];
void w_set()
{
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
for(int k = 0;k < N;k++)
{
if(i == 0 || j == 0 || k == 0) w[i][j][k] = 1;
else if(i < j && j < k) w[i][j][k] = w[i][j][k - 1] + w[i][j - 1][k - 1] - w[i][j - 1][k];
else w[i][j][k] = w[i - 1][j][k] + w[i - 1][j - 1][k] + w[i - 1][j][k - 1] - w[i - 1][j-1][k - 1];
}
}
int W(int a,int b,int c)
{
if(a <= 0 || b <= 0 || c <= 0) a = b = c = 0;
else
if(a > 20 || b > 20 || c > 20) a = b = c = 20;
return w[a][b][c];
}
int main()
{
w_set();
int a,b,c;
while(1)
{
scanf("%d%d%d",&a,&b,&c);
if(a == -1 && b == -1 && c == -1) break;
printf("w(%d, %d, %d) = %d\n",a,b,c,W(a,b,c));
}
return 0;
}

• @ 2021-08-26 12:06:49
``````#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll rpt[25][25][25];
ll w(ll a,ll b,ll c)
{
if(a<=0||b<=0||c<=0)
return 1;
else if(rpt[a][b][c]!=0)
return rpt[a][b][c];
else if(a>20 || b>20 || c>20)
rpt[a][b][c]=w(20,20,20);
else if(a<b && b<c)
rpt[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else
rpt[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 rpt[a][b][c];
}

int main()
{
ll a,b,c;
while(scanf("%lld%lld%lld",&a,&b,&c)==3){
memset(rpt,0,sizeof(rpt));
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));
}
return 0;
}
``````
• @ 2020-10-11 20:00:14

注意：用long long

``````#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

namespace dts
{
typedef long long ll;

ll a,b,c,vis[21][21][21],wv[21][21][21];

ll w(ll a,ll b,ll c)
{
if (a<=0||b<=0||c<=0)
{
vis[0][0][0]=1;
return (wv[0][0][0]=1);
}
else if (a>20||b>20||c>20)
return w(20,20,20);
else if (vis[a][b][c])
return wv[a][b][c];
vis[a][b][c]=1;
if (a<b&&b<c)
return (wv[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c));
else
return (wv[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));
}

void main()
{
memset(vis,0,sizeof(vis)),memset(wv,0,sizeof(wv));
while (~scanf("%lld%lld%lld",&a,&b,&c))
if (a==-1&&b==-1&&c==-1)
break;
else
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
}
}

int main()
{
dts::main();
}
``````

注意：用long long

• @ 2018-08-01 14:16:16

注意一下规则的优先级。。
我把>20就返回w(20,20,20)写在最前面就WA了。。
因为这时候可能也满足有数字<=0，要先判断这一条规则。

``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int a,b,c;
bool vis[21][21][21];
ll f[21][21][21];
ll work(int a,int b,int c) {
if (a<=0||b<=0||c<=0) {
return 1;
}
if (a>20||b>20||c>20) {
a=b=c=20;
}
if (vis[a][b][c]) return f[a][b][c];
vis[a][b][c]=1;
ll res=0;
if (a<b&&b<c) {
res=work(a,b,c-1)+work(a,b-1,c-1)-work(a,b-1,c);
f[a][b][c]=res;
return res;
} else {
res=work(a-1,b,c)+work(a-1,b-1,c)+work(a-1,b,c-1)-work(a-1,b-1,c-1);
f[a][b][c]=res;
return res;
}
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while (scanf("%d%d%d",&a,&b,&c)==3) {
if (a==-1&&b==-1&&c==-1) break;
printf("w(%d, %d, %d) = %lld\n",a,b,c,work(a,b,c));
}
return 0;
}
``````
• @ 2018-05-30 20:32:56

此题记忆化搜索
要剪枝！要剪枝！要剪枝！
否者数据过不去

``````#include<stdio.h>
int w[21][21][21] = {1};    //用数组储存结果
int getw(int a, int b, int c)
{
if(a <= 0 || b <= 0 || c <= 0)
return 1;
else if(a > 20 || b > 20 || c > 20)
return w[20][20][20];
else
return w[a][b][c];
return 1;
}
int main(){
int a, b, c;
for(a = 1; a <= 20; ++a){
for(b = 1; b <= 20; ++b){
for(c = 1; c <= 20; ++c){
if(a < b && b < c){
w[a][b][c] = getw(a, b, c-1) + getw(a, b-1, c-1) - getw(a, b-1, c);
}else{
w[a][b][c] = getw(a-1, b, c) + getw(a-1, b-1, c) + getw(a-1, b, c-1) - getw(a-1, b-1, c-1);
}
}
}
}
while(scanf("%d%d%d", &a, &b, &c) && (a + 1) || (b + 1) || (c + 1))
printf("w(%d, %d, %d) = %d\n", a, b, c, getw(a, b, c));
return 0;
}

``````
• @ 2017-05-07 22:39:36
``````/*
水题啊
直接记忆化搜索就好了
然后按照他的要求来返回值就行了
不多说惹
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=30;
int f[MAXN][MAXN][MAXN];
bool v[MAXN][MAXN][MAXN];
int a,b,c;

int dfs(int x,int y,int z)
{
if(x<=0||y<=0||z<=0)
return 1;
if(x>20||y>20||z>20)
return dfs(20,20,20);
if(v[x][y][z])
return f[x][y][z];
v[x][y][z]=1;
if(a<b&&b<c)
return f[x][y][z]=dfs(x,y,z-1)+dfs(x,y-1,z-1)+dfs(x,y-1,z);
else
return f[x][y][z]=dfs(x-1,y,z)+dfs(x-1,y-1,z)+dfs(x-1,y,z-1)-dfs(x-1,y-1,z-1);
}

int main()
{
while(cin>>a>>b>>c)
{
if(a==-1&&b==-1&&c==-1)
break;
else
printf("w(%d, %d, %d) = %d\n",a,b,c,dfs(a,b,c));
}
}

``````
• @ 2017-04-11 22:17:04

en就是考一个简单的记忆化
楼下说的非常好
附pascal代码：

``````var
a,b,c,i,j,k,impossible:longint;
v:array[-10..30,-10..30,-10..30] of longint;

function fun(a,b,c:longint):longint;
begin
if (a<=0) or (b<=0) or (c<=0) then exit(1);
if (a>20) or (b>20) or (c>20) then exit(fun(20,20,20));
if v[a,b,c]<>impossible then exit(v[a,b,c])
else
begin
if (a<b) and (b<c) then
begin
v[a,b,c]:=fun(a,b,c-1)+fun(a,b-1,c-1)-fun(a,b-1,c);
exit(v[a,b,c]);
end
else
begin
v[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);
exit(v[a,b,c]);
end;
end;
end;
begin
impossible:=-maxlongint;
for i:= -10 to 30 do
for j:= -10 to 30 do
for k:= -10 to 30 do
v[i,j,k]:=impossible;
while true do
begin
if (a=-1) and (b=-1) and (c=-1) then break;
writeln('w(',a,', ',b,', ',c,') = ',fun(a,b,c));
end;
end.
``````
• @ 2016-03-22 07:14:52

测试数据 #0: Accepted, time = 0 ms, mem = 680 KiB, score = 100

Accepted, time = 0 ms, mem = 680 KiB, score = 100

• @ 2015-08-23 18:48:26

记录信息
评测状态 Accepted
题目 P1080 Function(Function(F...
递交时间 2015-08-23 18:48:04
代码语言 C++
评测机 Jtwd2
消耗时间 0 ms
消耗内存 616 KiB
评测时间 2015-08-23 18:48:05
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 616 KiB, score = 100
Accepted, time = 0 ms, mem = 616 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
int f[30][30][30];
bool been[30][30][30];
int w(int a,int b,int c)
{
if(a<=0||b<=0||c<=0)return 1;
if(a>20||b>20||c>20)return w(20,20,20);
if(been[a][b][c])return f[a][b][c];
been[a][b][c]=true;
if(a<b&&b<c) return f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
return 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);
}
int main()
{
int a,b,c;
while(888)
{
scanf("%d%d%d",&a,&b,&c);
if(a==-1&&b==-1&&c==-1)break;
printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
}
}

• @ 2015-08-11 16:32:04

为何会WA？
本地运行完全正确的啊

program P1080;
var a,b,c:longint;
k:array[0..20,0..20,0..20] of longint;

function w(a,b,c:longint):longint;
begin
if (a<=0) or (b<=0) or (c<=0) then exit(1);
if (a>20) or (b>20) or (c>20) then exit(w(20,20,20));
if k[a,b,c]<>-maxlongint then exit(k[a,b,c]);
if (a<b) and (b<c) then begin
k[a,b,c]:=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
exit(k[a,b,c]);
end;
k[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);
exit(k[a,b,c]);
end;

BEGIN
for a:=0 to 20 do
for b:=0 to 20 do
for c:=0 to 20 do
k[a,b,c]:=-maxlongint;
while (a<>-1) and (b<>-1) and (c<>-1) do begin
writeln('w(',a,', ',b,', ',c,') = ',w(a,b,c));
end;
END.

• @ 2015-08-11 16:30:31

为何会WA？
本地运行完全正确的啊

program P1080;
var a,b,c:longint;
k:array[0..20,0..20,0..20] of longint;

function w(a,b,c:longint):longint;
begin
if (a<=0) or (b<=0) or (c<=0) then exit(1);
if (a>20) or (b>20) or (c>20) then exit(w(20,20,20));
if k[a,b,c]<>-maxlongint then exit(k[a,b,c]);
if (a<b) and (b<c) then begin
k[a,b,c]:=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
exit(k[a,b,c]);
end;
k[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);
exit(k[a,b,c]);
end;

BEGIN assign(input,'p1080.in'); reset(input); assign(output,'a1.txt'); rewrite(output);
for a:=0 to 20 do
for b:=0 to 20 do
for c:=0 to 20 do
k[a,b,c]:=-maxlongint;
while (a<>-1) and (b<>-1) and (c<>-1) do begin
writeln('w(',a,', ',b,', ',c,') = ',w(a,b,c));
end; close(input); close(output);
END.

• @ 2015-08-11 16:31:17

文件是调试时写上去的

• @ 2015-07-24 20:09:23

记忆化搜索，注意判断一个条件后就不必判断后面的条件，而且必须按顺序判断。
var x,y,z,i,j,k,l:longint; a:array[0..20,0..20,0..20]of longint;
function pd:boolean;
begin
if (x=-1)and(y=-1)and(z=-1) then exit(false);
exit(true);
end;
function w(x,y,z:longint):longint;
begin
if (x<=0)or(y<=0)or(z<=0) then exit(1);
if (x>20)or(y>20)or(z>20) then exit(w(20,20,20));
if a[x,y,z]<>-maxlongint then exit(a[x,y,z]);
if (x<y)and(y<z) then begin a[x,y,z]:=(w(x,y,z-1)+w(x,y-1,z-1)-w(x,y-1,z));exit(a[x,y,z])end;
a[x,y,z]:=w(x-1,y,z)+w(x-1,y-1,z)+w(x-1,y,z-1)-w(x-1,y-1,z-1); exit(a[x,y,z]);
end;
begin
for i:=0 to 20 do
for j:=0 to 20 do
for k:=0 to 20 do
a[i,j,k]:=-maxlongint;
while pd=true do
begin
j:=w(x,y,z);
writeln('w(',x,', ',y,', ',z,') = ',j);
end;
end.

• @ 2014-10-31 22:14:23

P1080Function(Function(F...
Accepted

记录信息

评测状态 Accepted
题目 P1080 Function(Function(F...
递交时间 2014-10-31 22:13:43
代码语言 C++
评测机 VijosEx
消耗时间 0 ms
消耗内存 364 KiB
评测时间 2014-10-31 22:13:44

评测结果

编译成功

foo.cpp: In function 'long long unsigned int f(int, int, int)':
foo.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( w[a][b][c] != -1 )
^
foo.cpp: In function 'int main()':
foo.cpp:36:71: warning: unknown conversion type character 'l' in format [-Wformat=]
printf( "w(%d, %d, %d) = %llu\n" , a , b , c , f( a , b , c ) );
^
foo.cpp:36:71: warning: too many arguments for format [-Wformat-extra-args]

测试数据 #0: Accepted, time = 0 ms, mem = 364 KiB, score = 100

Accepted, time = 0 ms, mem = 364 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

unsigned long long w[20 + 2][20 + 2][20 + 2];
int a , b , c;

unsigned long long f( int a , int b , int c )
{
if( a <= 0 || b <= 0 || c <= 0 )
return 1;
if( a > 20 || b > 20 || c > 20 )
return f( 20 , 20 , 20 );
if( w[a][b][c] != -1 )
return w[a][b][c];
if( a < b && b < c )
{
w[a][b][c] = f( a , b , c - 1 ) + f( a , b - 1 , c - 1 ) - f( a , b - 1 , c );
return w[a][b][c];
}
w[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 );
return w[a][b][c];
}

int main()
{
memset( w , -1 , sizeof( w ) );
while( scanf( "%d %d %d" , &a , &b , &c ) != EOF )
{
if( a == -1 && b == -1 && c == -1 )
break;
printf( "w(%d, %d, %d) = %llu\n" , a , b , c , f( a , b , c ) );
}
return 0;
}

记忆化秒杀

• @ 2014-10-23 19:15:02

输出好多空格，注意别被坑了

• @ 2013-12-12 13:43:12

我恨输出格式：
#include<cstring>

#include<iostream>
using namespace std;
int m[21][21][21];

int w(int a1,int b1,int c1)
{
if(a1<=0||b1<=0||c1<=0)return 1;
if(a1>20||b1>20||c1>20)return w(20,20,20);
if(m[a1][b1][c1]!=0)return m[a1][b1][c1];
if(a1<b1&&b1<c1)m[a1][b1][c1]=w(a1,b1,c1-1)+w(a1,b1-1,c1-1)-w(a1,b1-1,c1);
else m[a1][b1][c1]=w(a1-1,b1,c1)+w(a1-1,b1-1,c1)+w(a1-1,b1,c1-1)-w(a1-1,b1-1,c1-1);
return m[a1][b1][c1];
}

int main()
{
int a,b,c,ans;
cin>>a>>b>>c;
if(a==-1&&b==-1&&c==-1)return 0;
memset(m,0,sizeof(m));
ans=w(a,b,c);
cout<<"w("<<a<<", "<<b<<", "<<c<<")"<<" = "<<ans<<endl;
main();
}
WA：2

• @ 2013-11-09 22:40:22

记忆化搜索
#include <cstdio>
int w[21][21][21];

int get_w(int a,int b,int c){
if (a<=0 || b<=0 || c<=0)
return 1;
if (a>20 || b>20 || c>20)
return w[20][20][20]=get_w(20,20,20);
if (w[a][b][c]!=-1)
return w[a][b][c];

if (a<b && b<c){
w[a][b][c-1]=get_w(a,b,c-1);
w[a][b-1][c-1]=get_w(a,b-1,c-1);
w[a][b-1][c]=get_w(a,b-1,c);
return w[a][b][c-1]+w[a][b-1][c-1]-w[a][b-1][c];
}

w[a-1][b][c]=get_w(a-1,b,c);
w[a-1][b-1][c]=get_w(a-1,b-1,c);
w[a-1][b][c-1]=get_w(a-1,b,c-1);
w[a-1][b-1][c-1]=get_w(a-1,b-1,c-1);
return w[a-1][b][c]+w[a-1][b-1][c]+w[a-1][b][c-1]-w[a-1][b-1][c-1];
}

int main(){
for (int i=0;i<=20;i++)
for (int j=0;j<=20;j++)
for (int k=0;k<=20;k++)
w[i][j][k]=-1;
w[0][0][0]=1;
int a,b,c;
for(;;){
scanf("%d%d%d",&a,&b,&c);
if (a==-1 && b==-1 && c==-1)
break;
int ans=get_w(a,b,c);
printf("w(%d, %d, %d) = %d\n",a,b,c,ans);
}

return 0;
}

• @ 2013-11-08 08:11:39

const
small=-2139062144;
var
f:array[0..20,0..20,0..20] of longint;
a,b,c,aa,bb,cc:longint;
function go(a,b,c:longint):longint;
begin
if (a<=0) or (b<=0) or (c<=0) then exit(1);
if (a>20) or (b>20) or (c>20) then exit(go(20,20,20));
if f[a,b,c]>small then exit(f[a,b,c]);

if (a<b) and (b<c) then
begin
f[a,b,c]:=go(a,b,c-1)+go(a,b-1,c-1)-go(a,b-1,c);
exit(f[a,b,c]);
end;
f[a,b,c]:=go(a-1,b,c)+go(a-1,b-1,c)+go(a-1,b,c-1)-go(a-1,b-1,c-1);
exit(f[a,b,c]);
end;
begin
fillchar(f,sizeof(f),128);
f[0,0,0]:=1;
while (a<>-1) or (b<>-1) or (c<>-1) do
begin
writeln('w(',a,', ',b,', ',c,') = ',go(a,b,c));
end;
end.

如此水题，我竟然WA了一次！
究其原因，我的优先级搞错了。
如果有一个>20,有一个<0,那么优先<0.
其他，就是注意空格的问题了。

• @ 2013-11-05 08:19:22

那个....请注意输出有空格。我就被坑了

• @ 2013-10-30 20:39:58

var a,b,c:Longint;
F:array[-100..100,-100..100,-100..100] of Longint;

Function W(a,b,c:Longint):Longint;
var Tmp:Longint;
Begin
If F[a,b,c]<>0 then Exit(F[a,b,c]) Else
If (a<=0)or(b<=0)or(c<=0) then Tmp:=1 Else
if (a>20)or(b>20)or(c>20) then Tmp:=W(20,20,20) Else
If (a<b)and(b<c) then Tmp:=W(a,b,c-1)+W(a,b-1,c-1)-W(a,b-1,c)
Else Tmp:=W(a-1,b,c)+W(a-1,b-1,c)+W(a-1,b,c-1)-w(a-1,b-1,c-1);
F[a,b,c]:=Tmp;
Exit(Tmp);
End;

Begin
While (a<>-1)or(b<>-1)or(c<>-1) do
Begin
Writeln('w(',a,', ',b,', ',c,') = ',w(a,b,c));
End;
End.

• @ 2013-10-03 15:34:36

好假，连数据规模都没写

ID
1080

6

(无)

3751

1123

30%

5