【题解】CF1185G1

是道中规中矩的状压dp

我们设 $dp_{i,j}$（ $i$ 是表示状态的二进制数）为组成“选了 $i$ 所表示的几首歌，并且以编号为$j$的歌曲结尾的歌单”的方案数。

我们考虑枚举歌单状态$i$和结尾歌曲编号$j$，并枚举新加入歌单，加在歌单结尾，并且不包含在歌单 $i$ 中的歌曲 $k$，并设 $x$ 为歌单 $i$ 加入歌曲 $k$ 后的状态表示（即x=i|(1<<(k-1))），易得出状态转移：dp[x][j]+=dp[i][j];

统计答案的话就是枚举状态，如果歌曲总长度等于 $T$ 的话就累加答案。

代码：

#include <iostream>
using namespace std;
#define int long long
const int MOD=1e9+7;
int n,T;
int t[20],g[20];
int dp[1<<18][5];
int ans=0;

signed main()

{
	cin>>n>>T;
	for (int i=1;i<=n;i++)
		cin>>t[i]>>g[i];

	dp[0][0]=1;
	for (int i=0;i<(1<<n);i++){
		for (int j=0;j<=3;j++){
			for (int k=1;k<=n;k++){
				if (i&(1<<k-1) || g[k]==j) continue;
				dp[i|(1<<k-1)][g[k]]+=dp[i][j];
				dp[i|(1<<k-1)][g[k]]%=MOD;
			}
		}
	}

    //统计答案
	for (int i=1;i<(1<<n);i++){
		int cnt=0;
		for (int j=1;j<=n;j++)
			if (i&(1<<j-1)) cnt+=t[j];

		if (cnt==T){
			ans+=dp[i][1]+dp[i][2]+dp[i][3];
			ans%=MOD;
		}
	}

	cout<<ans<<endl;
	return 0;
}