3864: Hero meet devil
题意:
给你一个只由AGCT组成的字符串S (|S| ≤ 15),对于每个0 ≤ .. ≤ |S|,问
有多少个只由AGCT组成的长度为m(1 ≤ m ≤ 1000)的字符串T,使得\(LCS(T,S) = i\)?
dp套dp!
通过一个外层的dp来计算使得另一个dp方程(子dp)最终结果为特定值的输入数。
一位一位确定子dp的输入,记录子dp的状态值
子dp:
\(d(i,j)\)表示\(LCS(T[1,i],S[1,j])\),对第二维差分,\(j\)与\(j-1\)只可能相差0/1,可以状压
外层dp:
\(f(i,s)\)表示确定到T的第i位,子dp状态值为s的方案数
预处理子dp每种状态值加一个字符后的转移,然后进行外层dp即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1005, mo = 1e9+7;
inline int read() {
char c=getchar(); int x=0,f=1;
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
int n, m; char str[20], c[10] = "ACGT";
int trans[1<<15][4], one[1<<15], f[2][1<<15];
void init() {
static int d[20], g[20];
for(int s=0; s < 1<<n; s++) {
if(s) one[s] = one[s ^ (s&-s)] + 1;
for(int j=0; j<n; j++) d[j+1] = d[j] + bool(s & (1<<j));
for(int k=0; k<4; k++) {
for(int j=1; j<=n; j++) {
g[j] = max(g[j-1], d[j]);
if(c[k] == str[j]) g[j] = max(g[j], d[j-1]+1);
}
trans[s][k] = 0;
for(int j=0; j<n; j++) if(g[j+1] - g[j]) trans[s][k] |= 1<<j;
}
}
}
int ans[N];
int main() {
freopen("in", "r", stdin);
int T = read();
while(T--) {
scanf("%s", str+1); m = read(); n = strlen(str+1);
init();
memset(ans, 0, sizeof(ans));
memset(f, 0, sizeof(f));
f[0][0] = 1; int p = 0;
for(int i=1; i<=m; i++, p ^= 1) {
memset(f[p^1], 0, sizeof(f[p^1]));
for(int s=0; s < 1<<n; s++)
for(int k=0; k<4; k++) (f[p^1][trans[s][k]] += f[p][s]) %= mo;
}
for(int s=0; s < 1<<n; s++) (ans[one[s]] += f[p][s]) %= mo;
for(int i=0; i<=n; i++) printf("%d\n", ans[i]);
}
}
bzoj 3864: Hero meet devil [dp套dp]的更多相关文章
-
BZOJ 3864 Hero meet devil (状压DP)
最近写状压写的有点多,什么LIS,LCSLIS,LCSLIS,LCS全都用状压写了-这道题就是一道状压LCSLCSLCS 题意 给出一个长度为n(n<=15)n(n<=15)n(n< ...
-
BZOJ 3864 Hero meet devil 超详细超好懂题解
题目链接 BZOJ 3864 题意简述 设字符集为ATCG,给出一个长为\(n(n \le 15)\)的字符串\(A\),问有多少长度为\(m(m \le 1000)\)的字符串\(B\)与\(A\) ...
-
bzoj 3864: Hero meet devil(dp套dp)
题面 给你一个只由\(AGCT\)组成的字符串\(S (|S| ≤ 15)\),对于每个\(0 ≤ .. ≤ |S|\),问 有多少个只由\(AGCT\)组成的长度为\(m(1 ≤ m ≤ 1000) ...
-
bzoj 3864: Hero meet devil
bzoj3864次元联通们 第一次写dp of dp (:з」∠) 不能再颓废啦 考虑最长匹配序列匹配书转移 由于dp[i][j]的转移可由上一行dp[i-1][j-1],dp[i-1][j],dp[ ...
-
BZOJ 3864 Hero Meets Devil
题目大意 给定一个由AGCT组成的串\(t\), 求对于所有的\(L \in [1, |t|]\), 有多少个由AGCT组成的串\(s\)满足\(LCS(s, t) = L\). Solution 传 ...
-
HDU 4899 Hero meet devil (状压DP, DP预处理)
题意:给你一个基因序列s(只有A,T,C,G四个字符,假设长度为n),问长度为m的基因序列s1中与给定的基因序列LCS是0,1......n的有多少个? 思路:最直接的方法是暴力枚举长度为m的串,然后 ...
-
【BZOJ3864】Hero meet devil DP套DP
[BZOJ3864]Hero meet devil Description There is an old country and the king fell in love with a devil ...
-
DP套DP
DP套DP,就是将内层DP的结果作为外层DP的状态进行DP的方法. [BZOJ3864]Hero meet devil 对做LCS的DP数组差分后状压,预处理出转移数组,然后直接转移即可. tr[S] ...
-
[模板] dp套dp &;&; bzoj5336: [TJOI2018]party
Description Problem 5336. -- [TJOI2018]party Solution 神奇的dp套dp... 考虑lcs的转移方程: \[ lcs[i][j]=\begin{ca ...
随机推荐
-
[bzoj3932][CQOI2015][任务查询系统] (主席树)
Description 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的 任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si ...
-
iOS,一行代码进行RSA、DES 、AES、MD5加密、解密
本文为投稿文章,作者:Flying_Einstein(简书) 加密的Demo,欢迎下载 JAVA端的加密解密,读者可以看我同事的这篇文章:http://www.jianshu.com/p/98569e ...
-
c++ 一些随笔
1. A region of source code where any use of the unqualified name (that is, as a plain identifier) re ...
-
SQL Server调优系列进阶篇(查询语句运行几个指标值监测)
前言 上一篇我们分析了查询优化器的工作方式,其中包括:查询优化器的详细运行步骤.筛选条件分析.索引项优化等信息. 本篇我们分析在我们运行的过程中几个关键指标值的检测. 通过这些指标值来分析语句的运行问 ...
-
iOS打包Framework真机和模拟器兼容合并版本 - 详细攻略步骤
打包Framework,测试时: 1.用模拟器打包,测试时只能跑在模拟器 2.用真机打包,测试时只能跑在真机 那么怎么做到一个版本兼容以上两种场景呢? 解决如下: 1.打开终端 2.输入 lipo ...
-
《JavaScript权威指南》学习笔记 第五天 window对象的方法。
前天和昨天大致浏览了犀牛书的函数.类与模块.正则表达式.JavaScript扩展.以及服务端的js.这些方面对于我目前的水平来说比较难,一些最基本的概念都不能领会.不过最复杂的知识占用平时使用的20% ...
-
ASIHttpRequest addRequestHeader的处理
我现在用到了ASIHttpRequest来读取数据,这时候我发现里面的头在很多时候都是一样的.如用户的令牌,设备类型,ios版本,软件版本等 [self.request addRequestHeade ...
-
不同数据库oracle mysql SQL Server DB2 infomix sybase分页查询语句
在不同数据库中的使用的分页查询语句: 当前页:currentpage 页大小:pagesize 1. Oracle数据库 select * from (select A.*,rownum rn fro ...
-
使用cocoapods的两个大坑的修改方法
1.报错内容: [!] The dependency `ReactiveCocoa (= 2.1.8)` is not used in any concrete target. The depende ...
-
改装原生的dialog
改装 dialog 定制 View rootView = LayoutInflater.from(mContext). inflate(R.layout.nfc_tag_name_dialog, nu ...