关键词：
这题是一道状压DP,暂时还不是很懂.
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int LENM=1010,N=11,M=1e9+7; char s[N]; int n,m,u,ind[200],f[LENM][1<<10],g[N],ans[N],gg[N],num1[1<<10],ff[1<<10][5]; int main(){ scanf("%s%d",s+1,&m); n=strlen(s+1); u=1<<n; f[0][0]=1; ind[‘A‘]=1; ind[‘C‘]=2; ind[‘G‘]=3; ind[‘T‘]=4; for (int i=1; i<=n; i++) s[i]=ind[s[i]]; for (int i=0; i<u; i++){ for (int k=1; k<=n; k++) g[k]=(1&(i>>k-1))+g[k-1]; for (int j=1; j<=4; j++){ int res=0; for (int k=1; k<=n; k++){ gg[k]=max(max(g[k-1]+(s[k]==j),gg[k-1]),g[k]); res|=(gg[k]-gg[k-1])<<k-1; } ff[i][j]=res; } } for (int i=0; i<m; i++) for (int j=0; j<u; j++) if (f[i][j]) for (int k=1; k<=4; k++) (f[i+1][ff[j][k]]+=f[i][j])%=M; for (int i=0; i<u; i++){ if (i) num1[i]=num1[i-1&i]+1; (ans[num1[i]]+=f[m][i])%=M; } for (int i=0; i<=n; i++) printf("%d ",ans[i]); }
一篇好的博客http://blog.csdn.net/HOWARLI/article/details/69487024
ybtoj状压dp课堂过关例题1jzoj1266luogup1879[usaco06nov]cornfieldsg&玉米田&种植方案(代码片段)
【例题1】种植方案&玉米田Link解题思路CodeLinkybtoj【状压DP课堂过关】【例题1】种植方案jzoj【1266】玉米田luogu【P1879】[USACO06NOV]CornFieldsG题面//因为不知道侵不侵权所以就是题面是私密的，有账号的直接看转送门就可了解题... 查看详情
jzoj5990.北大2019冬令营模拟2019.1.6bear（状压dp）(代码片段)
...只要有一个小trick就可以A了→_→。全场都插头dp就我一个状压跑得贼慢……不难发现我们可以状压，对于每一行，用状态(S)表示有哪些格子是已经被上一行推倒了的，那么我们可以枚举本行所有格子的字母情况，然后计算一下这... 查看详情
jzoj5230_队伍统计_dp
...10^9+7取模。 思路看到数据范围就应该可以想到可以用状压dp，我们用f[ 查看详情
jzoj5230.队伍统计(代码片段)
...<=n*(n-1)，保证矛盾关系不重复。 分析 一道状压DP（不会啊啊啊啊）考试时，稳稳地打了暴力30后来才理解状压，顾名思义就是要将一些状压想办法压缩起来（可以压，也可以删）。其中这些状态都 查看详情
状压dp小结
1.要状压的那一维，所有有关的下标要从0开始，而不是从1开始2.预处理很重要，可以说基本所有的状压dp都要有预处理这玩意 查看详情
hoj2662经典状压dp//myfirst状压dp
题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言：用dp解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。但是有这样的一类题目，它们具有dp问题的特性，但状态中所包含的信息过多，... 查看详情
动态规划---状压dp2(代码片段)
今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情
dp区间规划类问题jzoj1290关灯
状态多了一维的区间规划....注意处理好每一步的耗能#include<iostream>#include<string>#include<cstring>#include<algorithm>usingnamespacestd;intn;intf[2005][2005][3];intsum[2000006];intstdx[10000];inta[1 查看详情
状压dp(代码片段)
这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09 00001001&5 000001011 &nb 查看详情
foreignnumber[状压dp]
...leInput 123455SampleOutput 24HINT Solution 我们运用状压DP，令f[j][opt]表示当前余数为j，状态为opt的方案。 状态记录的是：各个数字被用了几次。 那么我们就可以状压了。先 查看详情
第一次接触状压dp(代码片段)
状压DP入门及理解*（另类的暴力）* 一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。 状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。 &... 查看详情
算法复习——状压dp
状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····... 查看详情
fzu2188状压dp
G-SimpleStringProblemTimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示： 转移方程：i是当前节点，j是下一步要走的节点 子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情
d.romanandnumbers(状压dp)(代码片段)
D.RomanandNumbers(状压dp)把nnn的每一位状压，问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情
poj2411mondriaan'sdream（状压dp）
【POJ2411】Mondriaan‘sDream（状压dp）TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情
simplestringproblem（状压dp）(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情
jzoj1003东莞市选2007拦截导弹——dp(代码片段)
题目：https://jzoj.net/senior/#main/show/1003只要倒推一下第一次上升的最长和第一次下降的最长就行了。不用n^2logn，枚举了j还要用树状数组找值比自己大的元素。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>... 查看详情