2018 CCPC 秦皇岛 I (状压DP)

题意：

首先t组数据（t<=5），一个n代表有n件东西，每个东西可以代表两个物品，商品或者袋子，每个都有个值，如果这个要代表袋子的话，当前就代表是容量，而且必须把其他几件不是袋子的物品放一些进来，容量必须正好装满，问你有多少种合法的方案，袋子中放入的物品不同也代表不同，同一件物品只能放入一个袋子

（n<=15）

Sample Input
3
3
1 1 1
5
1 1 2 2 3
10
1 2 3 4 5 6 7 8 9 10

Sample Output
7
15
127

思路：首先我们看数据范围我们就能想到是状压DP，但是我们不能直接去0 1代表哪些是背包物品，这样我们就不确定物品怎么放入背包，所以我们预处理，我们预处理出所有状态是否可以是一个已经放满的背包，并且枚举状态中哪一个才是背包，为了方便计算

weight[i] 代表该状态下所有物品的值的和

f[i] 代表该状态下可以是一个放满的背包的种数

dp[i] 代表该状态下合法的所有种数

我们可以利用weight 计算出 f[i],即我们枚举到当前位时，我们假设当前位是背包 weight[i]-a[i]==a[i] 如果是的话 f[i]++, 因为当前背包容量是a[i]，其他总和也是a[i]，即代表当前背包装满了

然后我们可以利用所有的单个装满的背包合并起来算出最后状态

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<map>

#define PI acos(-1.0)

#define E 1e-6

#define MOD 16007

#define INF 0x3f3f3f3f

#define N 16

#define LL long long

using namespace std;

int a[N];

int f[<<N];//组成袋子的合法方案数

int dp[<<N];//合法方案数

int weight[<<N];//第i种状态的重量

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        int n;

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        for(int i=;i<(<<n);i++){

            weight[i]=;

            f[i]=;

            dp[i]=1;

        }

        for(int i=;i<=n;i++)//n位数字

            for(int j=;j<(<<n);j++)//2^n种状态

                if( <<(i-) & j )//若第i位是1

                    weight[j]+=a[i];//记录第j个状态的重量

        for(int i=;i<=n;i++)//n位数字

            for(int j=;j<(<<n);j++)//2^n种状态

                if( <<(i-) & j )//若第i位是1

        if(weight[j]-a[i]==a[i])//如果第j个状态的重量减去第i个物品的重量等于第i个物品的重量说明选择第j个状态是一个合法的袋子

                f[j]++;

        for(int i=;i<(<<n);i++){//包裹2^n种状态

            int k=(<<n)--i;//与i相斥的状态

            for(int j=k;;j=(j-)&k){//选物品的状态且其不能选为包裹

                dp[i|j]+=dp[j]*f[i];

                if(j==)

                    break;

            }

        }

        printf("%d\n",dp[(<<n)-]);

    }

    return ;

}

巴特西

2018 CCPC 秦皇岛 I (状压DP)

最新文章

热门文章