首页 > 代码库 > lightoj1021_状压dp

lightoj1021_状压dp

2024-08-15 18:00:38   218人阅读

题目链接：http://lightoj.com/volume_showproblem.php?problem=1021

给定一个base进制和一个模数k，然后给个base进制下的数字，问这些数字全排列中(在base进制下)是k的倍数有几个。

容易想到状态dp[n][S][m]（S是数字出现的集合），表示前n位用了数字集S且模k余数是m的方案数。

利用 (xy)base % k = ( x*base+y ) % k = (( x%k ) * base + y) % k ，进行状态第三维的转移。

不过d[16][216][20]有2000多W的状态数，且不说超时的问题，内存早已超过限制了。

可以发现，S这一维其实就包含了n这一维的信息了，所以只要二维就能表示状态。

dp[m][S]表示，数字集为s且模k余数为m的方案数

状态的转移，从前往后不好处理余数，所以我从后往前更新状态的值，所谓的“我为人人”：

从dp[m][S]出发，更新dp[(m*base+y)%k][S‘]，其中S‘-S={y}。

技术分享
 1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define INF 0x3f3f3f3f14 typedef long long LL;15 16 char a[20];17 int b[20];18 LL dp[1<<16][25];19 int main()20 {21     int t, base, k;22     scanf("%d", &t);23     for(int ca = 1; ca <= t; ca++)24     {25         scanf("%d %d %s", &base, &k, a);26         int len = strlen(a);27         for(int i = 0; i < len; i++)28             if(a[i] >= ‘0‘ && a[i] <= ‘9‘)29                 b[i] = a[i] - ‘0‘;30             else31                 b[i] = a[i] - ‘A‘ + 10;32         memset(dp, 0, sizeof(dp));33         dp[0][0] = 1;34         for(int i = 0; i < (1 << len); i++)35         {36             for(int j = 0; j < len; j++)37             {38                 if(i & (1 << j))39                     continue;40                 for(int l = 0; l < k; l++)41                 {42                     if(dp[i][l] == 0)43                         continue;44                     dp[i | (1<<j)][(l*base+b[j])%k] += dp[i][l];45                 }46             }47         }48         printf("Case %d: %lld\n", ca, dp[(1<<len)-1][0]);49     }50     return 0;51 }
View Code

 

lightoj1021_状压dp


联系
我们