LOJ#3084. 'GXOI/GZOI 2019'보물패 무더기(밀어냄)

제면

전송문

문제풀이

왜 또 마작이야!그것도 내가 제일 싫어하는 검색어\(dp\)...
우선 국사 무쌍과 일곱 쌍은 직접 없앨 수 있는데, 관건은 남은 것이고, 관건은 참새 머리에 막대기나 체면이라고 볼 수 있다.
직접\(dp\), 설정\(f[i][j][k][l][x][y]\)는 전\(i\)종패를 고려하는 것을 표시하고, 제\(i-2\)종패로 시작하는 순자장수는\(j\),\(i-1\)로 시작하는 순자장수는\(k\),\(i\)로 시작하는 순자장수는\(l\), 바구니에 체면을 더하는 총수는\(x\), 참새 머리수는\y\(y\y)로 시작하는 최대값이다.
예를 들어 어떤 카드로 시작하는 순자가\(2\)개를 초과할 필요가 없다.\(3\)개를 선택하면 완전히 조각으로 분해할 수 있기 때문이다.그리고 어떤 패로 시작하는 순자는 비합법적일 수도 있다.그리고 카드 수를 합치면 초과할 수 없어요.
여기는 사실\(l\) 1차원을 스크롤 그룹으로 스크롤할 수 있습니다.
코드는 기본적으로 모두 베끼기\(fcw\)의 것이다

//minamoto
#include
#define R register
#define ll long long
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;iI;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
templateinline bool cmax(T&a,const T&b){return ay?x:y;}
ll bin[N],C[N][N];int a[N],b[N];
inline ll ch(R int x,R int v){return C[a[x]][v]*bin[b[x]*v];}
int id(char *w){
    if(strlen(w+1)==2){
        switch(w[2]){
            case 'm':return w[1]-'0';
            case 'p':return 9+w[1]-'0';
            case 's':return 18+w[1]-'0';
        }
    }else{
        switch(w[1]){
            case 'E':return 28;
            case 'W':return 29;
            case 'N':return 30;
            case 'S':return 31;
            case 'Z':return 32;
            case 'B':return 33;
            case 'F':return 34;
        }
    }
    return -1;
}
ll c[N];
ll solve1(){
    ll res=1;
    fp(i,1,34)c[i]=ch(i,2);
    sort(c+1,c+1+34);
    fp(i,28,34)res*=c[i];return res*7;
}
int d[20]={0,1,9,10,18,19,27,28,29,30,31,32,33,34};
ll solve2(){
    ll res=0,tmp;
    fp(i,1,13){
        tmp=ch(d[i],2);
        fp(j,1,13)if(i!=j)tmp*=ch(d[j],1);
        cmax(res,tmp);
    }return res*13;
}
ll f[35][3][3][5][2];
ll solve3(){
    memset(f,0,sizeof(f)),f[0][0][0][0][0]=1;
    fp(i,0,34){
        fp(j,0,2)if(!j||(i<=27&&i%9!=0&&i%9!=1)){
            fp(k,0,2)if(!k||(i<=27&&i%9!=8&&i%9!=0))
                if(a[i+1]>=j+k){
                    fp(x,j+k,4)fp(y,0,1)if(f[i][j][k][x][y]){
                            for(R int z=0;z<=2&&j+k+z<=a[i+1]&&x+z<=4;++z)
                                for(R int w=0;j+k+z+w*3<=a[i+1]&&x+z+w<=4;++w){
                                    int t=j+k+z+w*3;
                                    cmax(f[i+1][k][z][x+z+w][y],f[i][j][k][x][y]*ch(i+1,t));
                                    if(!y&&t+2<=a[i+1])cmax(f[i+1][k][z][x+z+w][1],f[i][j][k][x][y]*ch(i+1,t+2));
                                }
                            if(a[i+1]-j-k==4&&x<4)cmax(f[i+1][k][0][x+1][y],f[i][j][k][x][y]*ch(i+1,4));
                        }
                }
        }
    }
    return f[34][0][0][4][1];
}
void init(){
    bin[0]=1;fp(i,1,18)bin[i]=bin[i-1]<<1;
    fp(i,0,4){
        C[i][0]=1;
        fp(j,1,i)C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
}
char w[15];
void solve(){
    fp(i,1,34)a[i]=4,b[i]=0;
    while(true){
        scanf("%s",w+1);
        if(w[1]=='0')break;
        --a[id(w)];
    }
    while(true){
        scanf("%s",w+1);
        if(w[1]=='0')break;
        b[id(w)]=1;
    }
    printf("%lld
",max(solve1(),max(solve2(),solve3())));
}
int main(){
//  freopen("testdata.in","r",stdin);
    int T;scanf("%d",&T);init();
    while(T--)solve();
    return 0;
}

전재 대상:https://www.cnblogs.com/bztMinamoto/p/10719609.html