首页 > 代码库 > CodeForces 757D Felicity's Big Secret Revealed(状压DP)
CodeForces 757D Felicity's Big Secret Revealed(状压DP)
题意:给定一个01串,一个有效的n切割定义如下:一个横杠代表一次切割,第一条横杠前面的01串不算,最后一条横杠后面的01串不算,将两个横杠中的01串转化成十进制数字,假设这些数字的最大值是MAX且这些数字囊括了1-MAX的所有数字,则称为一次有效切割。求2~n+1次有效切割的切法。
思路: 由于题目要求包含所有1—MAXN的数字,且n<=75,所以MAXN<=20。另dp[i][j]表示第i位前面有一个横杆且存在j这个状态,接着从第i位开始枚举到第j位为下一个横杆的位置,设这两段横杆之间的数字为p(十进制),则递推式子为
dp[j+1][k|(1<<p-1)]+=dp[i][k],k为1~(1<<20)的状态。最后把dp[i][(1<<t)-1](0<=i<=n,1<=t<=20)加起来就可以了。
1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm> 10 #include <cmath> 11 #include <cstring> 12 #include <cstdlib> 13 #include <string> 14 #include <sstream> 15 #include <time.h> 16 #define x first 17 #define y second 18 #define pb push_back 19 #define mp make_pair 20 #define lson l,m,rt*2 21 #define rson m+1,r,rt*2+1 22 #define mt(A,B) memset(A,B,sizeof(A)) 23 #define mod 1000000007 24 using namespace std; 25 typedef long long LL; 26 const double PI = acos(-1); 27 const int N=1e5+10; 28 const int inf = 0x3f3f3f3f; 29 const LL INF=0x3f3f3f3f3f3f3f3fLL; 30 int dp[80][(1<<20)+10]; 31 int a[100]; 32 int main() 33 { 34 #ifdef Local 35 freopen("data","r",stdin); 36 #endif 37 int n,p,ans=0; 38 cin>>n; 39 mt(dp,0); 40 for(int i=0;i<n;i++)scanf("%1d",&a[i]); 41 for(int i=0;i<n;i++) 42 { 43 dp[i][0]=1; 44 for(int k=0;k<(1<<20);k++) 45 { 46 if(!dp[i][k])continue; 47 for(int j=i,p=a[i];j<n&&p<=20;j++,p=((p<<1)+a[j])) 48 { 49 if(p)dp[j+1][k|(1<<p-1)]=(dp[j+1][k|(1<<p-1)]+dp[i][k])%mod; 50 } 51 } 52 } 53 for(int i=0;i<=n;i++) 54 { 55 for(int k=1;k<=20;k++) 56 { 57 ans=(ans+dp[i][(1<<k)-1])%mod; 58 } 59 } 60 cout<<ans<<endl; 61 #ifdef Local 62 cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; 63 #endif 64 }
CodeForces 757D Felicity's Big Secret Revealed(状压DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。