G1. Playlist for Polycarp (easy version)(状压dp)

太过爱你忘了你带给我的痛 2022-01-05 08:37 186阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。

### 题目链接：[http://codeforces.com/contest/1185/problem/G1][http_codeforces.com_contest_1185_problem_G1] ###

题目大意是说，给你ｎ首歌曲的时间和类型。给你一个总的时间Ｔ。让你从ｎ首歌曲中选择任意几首歌曲。使之时间和等于总的时间，求满足的条件的次数。不可以连续选择同一种类型的歌曲。

dfs暴力超时。一看到这种题就想暴力。555  
事后才知道是状压dp。  
看到题目数据范围，自己就应该想到的。n小于15。这不就是用二进制的每一位来表示这首歌是否选择了吗。  
我们定义一个dpmask\]\[las\]的dp数组。  
其中mask是表示每首歌的选择情况。las是表示最后选择的歌曲是哪一个类别。  
dp\[mask\]\[las\]表示这样的选择方案有多少种。  
很明显了。dp的推导公式应该为：  
dp\[mask ^ (1 << j)\]\[g\[j\]\] += dp\[mask\]\[las\];  
如果，这个数组正确推导。然后，在遍历数组一次，同时求出所有选择方案的时间和等于T 的次数和。  
初始值，应该把dp\[0\]\[0\] = 1；

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"map"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    #define mod 1000000007
    
    int n,T;
    int t[20],g[20];
    int dp[1 << 20][4];
    
    int main()
    {
        scanf("%d%d",&n,&T);
        for(int i = 0; i < n; i ++)
            scanf("%d%d",&t[i],&g[i]);
        dp[0][0] = 1; //不可盲目的赋初值
        ll cnt = 0;
        for(int i = 0; i < (1 << n); i ++)
        {
            for(int k = 0; k <= 3; k ++)
            {
                for(int j = 0; j < n; j ++)
                {
                //对于一个位运算而言，这里要十分的主意，一定要打括号！！！！! 
                    if((g[j] != k) && ((i & (1 << j)) == 0))
                    {
                        dp[i ^ (1 << j)][g[j]] += dp[i][k];
                        dp[i ^ (1 << j)][g[j]] %= mod;
                    }
                }
                int sum = 0;
                for(int k = 0; k < n; k ++)
                {
                //同理这里也是位运算
                    if((i & (1 << k)) != 0)
                    {
                        sum += t[k];
                    }
                }
                if(sum == T)
                {
                    cnt += dp[i][k];
                    cnt %= mod;
                }
            }
        }
    
        printf("%I64d\n",cnt);
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[http_codeforces.com_contest_1185_problem_G1]: http://codeforces.com/contest/1185/problem/G1