状态压缩DP题目小节（二）

最近做的状态压缩DP小节：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4257

zoj 4257

一堆气体相互碰撞产生能量，求最后能产生的最大能量，应该是很基础的状态压缩DP吧，设dp[flag]表示状态flag时能产生的最大能量，（flag中1表示该气体还存在，0表示该气体已经消失）边界条件是flag所有位都为一时，这时产生的能量为0，然后就枚举最后剩下的气体，求最大值即可。

#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>#define maxn 100010#define ll long longusing namespace std;ll dp[14][14][1<<13];ll way[14][14][1<<13];int bo[14][14];int v[14];void init(){    memset(bo,0,sizeof(bo));    memset(way,0,sizeof(way));    memset(dp,-1,sizeof(dp));}ll max(ll a,ll b){    return a>b?a:b;}int n;ll dfs(int now,int pre,int flag){   // printf("f");    if(dp[now][pre][flag]!=-1)    return dp[now][pre][flag];    if(1<<(now-1)==flag)    {        way[now][pre][flag]=1;        return dp[now][pre][flag]=v[now];    }    int i,tru=0;    ll ans=0;    for(i=1;i<=n;i++)    {        if(i!=now&&i!=pre&&(flag&(1<<(i-1))))        {            tru=1;            if(bo[i][pre])            {                ll tmp=0;                tmp=dfs(pre,i,flag^(1<<(now-1)));                if(tmp)                {                    tmp+=v[now]+v[now]*v[pre];                    if(bo[i][now])                    tmp+=v[now]*v[pre]*v[i];                    ans=max(ans,tmp);                }            }        }    }    if(!tru)    {        dp[now][pre][flag]=dfs(pre,0,flag^(1<<(now-1)))+v[now]+v[now]*v[pre];        way[now][pre][flag]=1;        return dp[now][pre][flag];    }    if(ans)    {        for(i=1;i<=n;i++)        {            if(i!=now&&i!=pre&&bo[i][pre]&&(flag&(1<<(i-1))))            {                ll tmp=0;                tmp=dfs(pre,i,flag^(1<<(now-1)));                if(tmp)                {                    tmp+=v[now]+v[now]*v[pre];                    if(bo[i][now])                    tmp+=v[now]*v[pre]*v[i];                    if(ans==tmp)                    {                        way[now][pre][flag]+=way[pre][i][flag^(1<<(now-1))];                    }                }            }        }    }    return dp[now][pre][flag]=ans;}int main(){    //freopen("dd.txt","r",stdin);    int ncase;    scanf("%d",&ncase);    while(ncase--)    {        int m,i,a,b,j;        init();        scanf("%d%d",&n,&m);        for(i=1;i<=n;i++)        scanf("%d",&v[i]);        for(i=0;i<m;i++)        {            scanf("%d%d",&a,&b);            bo[a][b]=bo[b][a]=1;        }        ll ans=0,num=0;        if(n==1)        printf("%d 1\n",v[1]);        else        {            for(i=1;i<=n;i++)            {                for(j=1;j<=n;j++)                {                    if(i!=j&&bo[i][j])                    {                        dfs(i,j,(1<<n)-1);                        ans=max(ans,dp[i][j][(1<<n)-1]);                    }                }            }            if(ans==0)            printf("0 0\n");            else            {                for(i=1;i<=n;i++)                {                    for(j=1;j<=n;j++)                    {                        if(i!=j&&bo[i][j]&&dp[i][j][(1<<n)-1]==ans)                        {                            num+=way[i][j][(1<<n)-1];                        }                    }                }                printf("%I64d %I64d\n",ans,num/2);            }        }    }    return 0;}