Codeforces Round #191(Div.2) E 문항

상태 압축 DP,sum,원래는 매거진이었는데 결과적으로 TLE가 되었다.

 1 #include <iostream>

 2 #include <cstring>

 3 #include <cstdio>

 4 #include <queue>

 5 #include <cstdlib>

 6 using namespace std;

 7 #define MOD 1000000007

 8 int p[10001];

 9 int hash[1<<24];

10 int sum[1<<24];

11 int k[3];

12 int lowbit(int t)

13 {

14     return t&(-t);

15 }

16 int main()

17 {

18     int n,m,i,j;

19     scanf("%d",&n);

20     for(i = 0; i < n; i ++)

21     {

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

23     }

24     scanf("%d",&m);

25     for(i = 1; i <= m; i ++)

26     {

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

28     }

29     if(m == 1) k[2] = k[1];

30     hash[0] = 1;

31     for(i = 0;i < n;i ++)

32     sum[1<<i] = p[i];

33     for(i = 1; i < (1<<n); i ++)

34     {

35         sum[i] = sum[i-lowbit(i)] + sum[lowbit(i)];

36         if(sum[i] == k[1]||sum[i] == k[2])

37             continue;

38         for(j = i; j > 0; j -= lowbit(j))

39         {

40             hash[i] += hash[i-lowbit(j)];

41             if(hash[i] > MOD)

42             hash[i] -= MOD;

43         }

44     }

45     printf("%d
",hash[(1<<n)-1]);

46     return 0;

47 }