165 条题解
-
5tootal (hzq) LV 9 @ 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;
} -
22021-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; }
-
22020-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
-
22018-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; }
-
22018-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; }
-
12017-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)); } }
-
02017-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 readln(a,b,c); if (a=-1) and (b=-1) and (c=-1) then break; writeln('w(',a,', ',b,', ',c,') = ',fun(a,b,c)); end; end.
-
02016-03-22 07:14:52@
测试数据 #0: Accepted, time = 0 ms, mem = 680 KiB, score = 100
Accepted, time = 0 ms, mem = 680 KiB, score = 100
-
02015-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));
}
} -
02015-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;
readln(a,b,c);
while (a<>-1) and (b<>-1) and (c<>-1) do begin
writeln('w(',a,', ',b,', ',c,') = ',w(a,b,c));
readln(a,b,c);
end;
END. -
02015-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;
readln(a,b,c);
while (a<>-1) and (b<>-1) and (c<>-1) do begin
writeln('w(',a,', ',b,', ',c,') = ',w(a,b,c));
readln(a,b,c);
end; close(input); close(output);
END. -
02015-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
readln(x,y,z);
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);
readln(x,y,z);
end;
readln;
readln;
end. -
02014-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;
}记忆化秒杀
-
02014-10-23 19:15:02@
输出好多空格,注意别被坑了
-
02013-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 -
02013-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;
} -
02013-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;
readln(a,b,c);
while (a<>-1) or (b<>-1) or (c<>-1) do
begin
writeln('w(',a,', ',b,', ',c,') = ',go(a,b,c));
readln(a,b,c);
end;
end.如此水题,我竟然WA了一次!
究其原因,我的优先级搞错了。
如果有一个>20,有一个<0,那么优先<0.
其他,就是注意空格的问题了。 -
02013-11-05 08:19:22@
那个....请注意输出有空格。我就被坑了
-
02013-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
Readln(a,b,c);
While (a<>-1)or(b<>-1)or(c<>-1) do
Begin
Writeln('w(',a,', ',b,', ',c,') = ',w(a,b,c));
Readln(a,b,c);
End;
End. -
02013-10-03 15:34:36@
好假,连数据规模都没写