题目描述

解法

搜索。

代码

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

const char* fin="mahjong.in";

const char* fout="mahjong.out";

const int inf=0x7fffffff;

const int maxn=33,maxa=13;

int i,j,k,l,n,tmp,ans=0,ans1=0,ans2=0;

char s[2];

struct mj{

    char d[2];

    int cnt,id;

}a[maxn];

int b[256][maxa],r[256][maxa];

int use,times;

int num=0;

char f[14][2];

bool cmp(mj a,mj b){

    return a.d[0]<b.d[0] || a.d[0]==b.d[0] && a.d[1]<b.d[1];

}

int next(int v){;

    k=v+1;

    while (k<n && !a[k].cnt) k++;

    return k;

}

void dfs(int v,int want){

    int i,j,k;

    bool bz=false;

    if (v==n){

        if (!use || b[use][times]>=tmp){

            ans+=tmp;

            b[use][times]-=tmp;

        }

        return;

    }

    if (a[v].cnt==0) {

        dfs(next(v),want);

        return ;

    }

    if (next(v)==-1) return;

    j=next(v);

    k=next(next(v));

    if (a[j].d[0]==a[v].d[0] && a[j].d[1]==a[v].d[1]+1){

        if (a[k].d[0]==a[v].d[0] && a[k].d[1]==a[v].d[1]+2) {

            a[v].cnt--;

            a[j].cnt--;

            a[k].cnt--;

            dfs(v,want);

            a[v].cnt++;

            a[j].cnt++;

            a[k].cnt++;

        }

        if (bz) return;

        if (want==0){

            if (a[v].d[1]>'1' && want==0){

                a[v].cnt--;

                a[j].cnt--;

                tmp=b[a[v].d[0]][a[v].d[1]-1-'0'];

                use=a[v].d[0];

                times=a[v].d[1]-1-'0';

                dfs(v,1);

                tmp=0;

                a[v].cnt++;

                a[j].cnt++;

            }

            if (bz) return;

            if (a[j].d[1]<'9' && want==0){

                a[v].cnt--;

                a[j].cnt--;

                tmp=b[a[j].d[0]][a[j].d[1]+1-'0'];

                use=a[v].d[0];

                times=a[v].d[1]+1-'0';

                dfs(v,1);

                tmp=0;

                a[v].cnt++;

                a[j].cnt++;

            }

            if (bz) return;

        }

    }

    if (a[j].d[0]==a[v].d[0] && a[j].d[1]==a[v].d[1]+2){

        if (want==0){

            a[v].cnt--;

            a[j].cnt--;

            tmp=b[a[j].d[0]][a[j].d[1]-1-'0'];

            use=a[v].d[0];

            times=a[j].d[1]-1-'0';

            dfs(v,1);

            tmp=0;

            a[v].cnt++;

            a[j].cnt++;

        }

    }

    if (bz) return;

    if (a[k].d[0]==a[v].d[0] && a[k].d[1]==a[v].d[1]+2){

        if (want==0){

            a[v].cnt--;

            a[k].cnt--;

            tmp=b[a[k].d[0]][a[k].d[1]-1-'0'];

            use=a[v].d[0];

            times=a[k].d[1]-1-'0';

            dfs(v,1);

            tmp=0;

            a[v].cnt++;

            a[k].cnt++;

        }

    }

    if (a[v].cnt==2 && want==0){

        a[v].cnt-=2;

        tmp=b[a[v].d[0]][a[v].d[1]-'0'];

        use=a[v].d[0];

        times=a[v].d[1]-'0';

        dfs(v,1);

        tmp=0;

        a[v].cnt+=2;

    }

    if (bz) return;

    if (a[v].cnt>=3){

        a[v].cnt-=3;

        int rans=ans;

        dfs(v,want);

        //if (rans<ans) bz=true;

        a[v].cnt+=3;

    }

    if (bz) return;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    n=0;

    for (i=0;i<256;i++) for (j=0;j<maxa;j++) b[i][j]=4;

    for (i=0;i<14;i++){

        scanf("%s",&s);

        if (s[1]=='w') b['w'][s[0]-'0']--;

        else if (s[1]=='p') b['p'][s[0]-'0']--;

        else b['s'][s[0]-'0']--;

        swap(s[0],s[1]);

        for (j=0;j<n;j++) if (s[0]==a[j].d[0] && s[1]==a[j].d[1]){

            a[j].cnt++;

            break;

        }

        if (j==n) {

            a[n].id=i;

            a[n].cnt=1;

            a[n].d[0]=s[0];

            a[n++].d[1]=s[1];

        }

    }

    sort(a,a+n,cmp);

    a[n].d[0]='0';

    a[n].d[1]='0';

    a[n].cnt=0;

    for (i=0;i<256;i++) for (j=0;j<maxa;j++) r[i][j]=b[i][j];

    for (j=0;j<n;j++){

        ans=0;

        for (k=0;k<256;k++) for (l=0;l<maxa;l++) b[k][l]=r[k][l];

        if (a[j].cnt){

            a[j].cnt--;

            for (i=0;i<n;i++){

                if (a[i].cnt>1){

                    a[i].cnt-=2;

                    tmp=0;

                    use=0;

                    times=0;

                    dfs(0,0);

                    a[i].cnt+=2;

                }

                if (a[i].cnt%3==1){

                    a[i].cnt-=1;

                    tmp=b[a[i].d[0]][a[i].d[1]-'0'];

                    use=a[i].d[0];

                    times=a[i].d[1]-'0';

                    dfs(0,1);

                    a[i].cnt+=1;

                }

            }

            a[j].cnt++;

        }

        if (ans>ans2 || ans==ans2 && a[j].id<ans1){

            ans1=a[j].id;

            ans2=ans;

        }

    }

    ans1++;

    printf("%d %d",ans1,ans2);

    return 0;

}

启发

耗时间的压轴题；

但NOIP喜欢考。

总结两点来优化程序复杂度；

1.首先要把题目所给的信息数据化，并用数据结构存储；

这里所说的数据结构并非高级数据结构，而是类似于桶、链表之类的，有助于搜索编程复杂度优化的合适的数据结构。

2.明确题目所求：在搜索的时候始终贯彻这个目的。