首页 > 代码库 > hdu 5117 状压DP

hdu 5117 状压DP

2024-08-11 21:15:41   221人阅读

题意：
有M个开关，控制着N个灯，触碰一下开关，会把他所控制的灯的状态改变。对于M个开关你可以选择碰一次或者不碰，求最后开着多少个灯的三次方的期望值E(X^3)*2^m

题解：原式显然可以分解成X3      X=（x1+x2+x3...+xn),其中xi表示第i个灯的状态，题目就转化为求各个状态下X的立方的和

而X的立方可以看成是（x1+x2+x3...+xn)*（x1+x2+x3...+xn)*（x1+x2+x3...+xn)也就是xi*xj*xk的和，那么我们只要求出对于所有xi*xj*xk在所有状态中能为1的方法数，也就是i,j,k三灯全亮的方法数，加起来就是答案。用dp[i][j][k][ste][2]转移ste表示三个灯的状态，最后一个数组表示从处理前i个开关到处理前i+1个开关的滚动数组转移，注意滚动数组的初始化和DP不合法的判断

//#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <vector>#include <algorithm>#include <iostream>#include <map>#include <queue>#include <stack>#include <cmath>typedef long long ll;#define CLR(x, v) sizeof (x, v, sizeof(x))using namespace std;const int INF = 0x5f5f5f5f;const int mod=1e9 + 7;const int maxn = 60;int t,n,m;int dp[maxn][maxn][maxn][10][2];bool gra[maxn][maxn];int main(){   //freopen("in","r",stdin);   cin>>t;   int cas = 0;   while(t--){        cas++;        scanf("%d%d",&n,&m);        int k,l;        memset(dp,0,sizeof(dp));        memset(gra,false,sizeof(gra));        for(int i = 1;i <= m;i++){            scanf("%d",&k);            while(k--){                scanf("%d",&l);                gra[i][l] = true;            }        }        int id = 0;        memset(dp, 0, sizeof dp);        for(int i = 1;i <= n;i++)            for(int j = 1 ;j <= n;j++)                for(int k = 1;k <= n;k++){                   // if(i == j||j == k||i == k) continue;                    dp[i][j][k][0][0] = 1;                }        for(int t = 1;t <= m;t++){             for(int i = 1;i <= n;i++)                for(int j = 1;j <= n;j++)                    for(int k = 1;k <= n;k++)                        for(int ste = 0;ste < 8;ste++)                            dp[i][j][k][ste][id^1] = 0;            for(int i = 1;i <= n;i++)                for(int j = 1;j <= n;j++)                    for(int k = 1;k <= n;k++){                       // if(i == j||j == k||i == k) continue;                        for(int ste = 0;ste < 8;ste++){                            if (dp[i][j][k][ste][id] == 0) continue;                            dp[i][j][k][ste][id^1] += dp[i][j][k][ste][id];                            dp[i][j][k][ste][id^1] %= mod;                            int ans = ste;                            if(gra[t][i])                                ans ^= 1;                            if(gra[t][j])                                ans ^= 2;                            if(gra[t][k])                                ans ^= 4;                            dp[i][j][k][ans][id^1] += dp[i][j][k][ste][id];                            dp[i][j][k][ans][id^1] %= mod;                           // cout<<t<<" "<<i<<" "<<j<<" "<<k<<" "<<ans<<" "<<dp[i][j][k][ans][id^1]<<endl;                        }                    }            id ^= 1;        }      //  cout<<n<<endl;        int sum = 0;        for(int i = 1;i <= n;i++)            for(int j = 1;j <= n;j++)                for(int k = 1;k <= n;k++){                    sum += dp[i][j][k][7][id];                    sum %= mod;                }        printf("Case #%d: %d\n",cas,sum);   }   return 0;}

 

hdu 5117 状压DP


联系
我们