DP MASK Technique
Each dice uses the same category for derivation
Because there are a total of 13 types of dice, and each category also has 13 types
And each category can only be selected once, which means all dice will definitely have one of the positions in the category
00000 Derivation
00001 –> The first dice uses the first category
00010 - > The second dice uses the first category... and so on
00100
01000
10000
Then it will derive into
00011 –> The first dice uses the first category, the second dice uses the second category
.....
00011 - > The second dice uses the first category, the first dice uses the second category
//====================================================================||
// ||
// ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 55
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
void BitPrint(int x){
for(int i=0;i<13;i++){
printf("%d",(x>>i)&1);
}Pln();
}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
struct dice{
int x\[6\];
}dices\[M\];
int grade\[M\]\[M\];
int cal(int x,int k){
int ans=0;
int ans6=0;
for(int i=0;i<5;i++){
if(dices\[x\].x\[i\]==k+1)ans+=k+1;
ans6+=dices\[x\].x\[i\];
}
if(k==6)return ans6;
else if(k<=5)return ans;
if(k==7){
for(int i=0;i<3;i++){
if(dices\[x\].x\[i\]==dices\[x\].x\[i+1\]&&dices\[x\].x\[i+1\]==dices\[x\].x\[i+2\]){
return ans6;
}
}
}
if(k==8){
for(int i=0;i<2;i++){
if(dices\[x\].x\[i\]==dices\[x\].x\[i+1\]&&dices\[x\].x\[i+1\]==dices\[x\].x\[i+2\]&&dices\[x\].x\[i+2\]==dices\[x\].x\[i+3\]){
return ans6;
}
}
}
if(k==9){
bool y=true;
for(int i=1;i<5;i++){
if(dices\[x\].x\[i\]!=dices\[x\].x\[i-1\]){
y=false;
break;
}
}
if(y)return 50;
}
if(k==10){
for(int i=4;i<=5;i++){
bool y=true;
for(int j=1+i-4;j<i;j++){
if(dices\[x\].x\[j\]!=dices\[x\].x\[j-1\]+1){y=false;break;}
}
if(y)return 25;
}
}
if(k==11){
bool y=true;
for(int i=1;i<5;i++){
if(dices\[x\].x\[i\]!=dices\[x\].x\[i-1\]+1){y=false;break;}
}
if(y)return 35;
}
if(k==12){
int a\[5\];
for(int i=0;i<5;i++)a\[i\]=dices\[x\].x\[i\];
bool y=false;
y|=(a\[0\]==a\[1\]&&a\[1\]==a\[2\])&&(a\[3\]==a\[4\]);
y|=(a\[0\]==a\[1\])&&(a\[2\]==a\[3\]&&a\[3\]==a\[4\]);
if(y)return 40;
}
return 0;
}
int dp\[1<<13\];
int bdp\[1<<13\];
int track\[1<<13\];
bool inq\[1<<13\];
int cbit(int x){
int ans=0;
for(int i=0;i<13;i++){
ans+=(x>>i)&1;
}
return ans;
}
void solve(){
Set(grade,0);
Set(dp,0);
Set(inq,0);
Set(bdp,0);
Set(track,-1);
for(int i=0;i<13;i++){
for(int j=0;j<13;j++){
grade\[i\]\[j\]=cal(i,j);
// debug("%d %d %d\\n",i,j,grade\[i\]\[j\]);
}
}
queue<int\> q;
q.push(0);
inq\[0\]=1;
while(!q.empty()){
int x=q.front();q.pop();
if(x==(1<<13)-1)continue;
// BitPrint(x);
int k=cbit(x);
for(int i=0;i<13;i++){
if(!((x>>i)&1)){
int n=dp\[x\];
int ns=x|(1<<i);
int bonus=0;
if(k==5&&n+grade\[i\]\[k\]>=63){
bonus=35;
}
if(grade\[i\]\[k\]+n+bonus>dp\[ns\]){
dp\[ns\]=grade\[i\]\[k\]+n+bonus;
bdp\[ns\]=bonus;
// if(bdp\[ns\]==35)BitPrint(ns);
track\[ns\]=i;
}
if(!inq\[ns\]){
q.push(ns);
inq\[ns\]=1;
}
}
}
inq\[x\]=0;
}
// debug("ok\\n");
int n=(1<<13)-1;
int ans\[15\];
Set(ans,0);
int k=12;
while(1){
int j=track\[n\];
ans\[k\]=grade\[j\]\[k\];
if(k==5)ans\[13\]=bdp\[n\];
n=n^(1<<j);
if(k<=0)break;
k--;
}
int all=0;
for(int i=0;i<14;i++)all+=ans\[i\];
for(int i=0;i<14;i++){
printf("%d ",ans\[i\]);
}printf("%d\\n",all);
}
int main() {
ios\_base::sync\_with\_stdio(0);
while(1){
for(int i=0;i<13;i++){
for(int j=0;j<5;j++){
if(scanf("%d",&dices\[i\].x\[j\])==-1)return 0;
}
sort(dices\[i\].x,dices\[i\].x+5);
}
solve();
}
}