165 条题解

  • 4
    @ 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;
    }

  • 1
    @ 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;
    }
    
  • 1
    @ 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

  • 1
    @ 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;
    }
    
  • 1
    @ 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;  
    } 
    
    
  • 1
    @ 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));
        }
    }
         
    
  • 0
    @ 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
            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. 
    
  • 0
    @ 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

  • 0
    @ 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));
    }
    }

  • 0
    @ 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;
    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.

  • 0
    @ 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;
    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.

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

      文件是调试时写上去的

  • 0
    @ 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
    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.

  • 0
    @ 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;
    }

    记忆化秒杀

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

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

  • 0
    @ 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

  • 0
    @ 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;
    }

  • 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;
    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.
    其他,就是注意空格的问题了。

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

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

  • 0
    @ 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
    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.

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

    好假,连数据规模都没写

信息

ID
1080
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
3753
已通过
1125
通过率
30%
被复制
7
上传者