BZOJ 1079 [SCOI2008]着色方案-白红宇

BZOJ 1079 [SCOI2008]着色方案

阅读量：4514 次

发布时间：2019-06-08

本文共 1693 字，大约阅读时间需要 5 分钟。

思路：如果把每种油漆看成一种状态，O（5^15）不行

DP[a][b][c][d][e][f]:a表示能凃一个的有多少个

b能凃2个的还有多少个

c能凃3个的还有多少个

d能凃4个的还有多少个

e能凃5个的还有多少个

last 上次凃的是：last个油漆。

所以这次如果选last-1个油漆的时候，数量还要减一，与上次不同

1 //#pragma comment(linker, "/STACK:167772160") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                14 // #include
                 
                  15 using namespace std;16 #define clc(a,b) memset(a,b,sizeof(a))17 #define LL long long18 void fre() { freopen("in.txt","r",stdin);}19 const int inf = 0x3f3f3f3f;20 const double eps = 1e-5;21 // const double pi = acos(-1);22 const LL mod = 1e9+7;23 inline int r(){24 int x=0,f=1;char ch=getchar();25 while(ch>'9'||ch<'0'){ if(ch=='-') f=-1;ch=getchar();}26 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}27 return x*f;28 }29 int A[16];30 LL dp[16][16][16][16][16][6];31 bool vis[16][16][16][16][16][6];32 33 LL work(int a,int b,int c,int d,int e,int last){34 LL tem;35 tem=0; 36 if((a|b|c|d|e)==0) return 1;37 if(vis[a][b][c][d][e][last]) return dp[a][b][c][d][e][last];38 if(a) 39 tem+=(a-(last==2))*work(a-1,b,c,d,e,1);40 if(b)41 tem+=(b-(last==3))*work(a+1,b-1,c,d,e,2);42 if(c)43 tem+=(c-(last==4))*work(a,b+1,c-1,d,e,3);44 if(d)45 tem+=(d-(last==5))*work(a,b,c+1,d-1,e,4);46 if(e)47 tem+=e*work(a,b,c,d+1,e-1,5);48 dp[a][b][c][d][e][last]=(tem%mod);49 vis[a][b][c][d][e][last]=true;50 return dp[a][b][c][d][e][last];51 }52 53 int main(){54 // fre();55 int n;56 while(~scanf("%d",&n)){57 // clc(dp,0);58 // clc(vis,0);59 // clc(A,0);60 for(int i=0;i