HDU 3341 Lost's revenge （AC自动机 + DP + 变进制/hash）题解
2024-09-01 20:44:31
题意：给你些分数串，给你一个主串，主串每出现一个分数串加一分，要你重新排列主串，最多几分
思路：显然这里开$40^4$去状压内存不够。但是我们自己想想会发现根本不用开那么大，因为很多状态是废状压，不是不存在的，那么可以考虑想办法简化状态。
一个是hash，直接打表所有子情况，用ha[][][][]表示出所有情况，那么直接dp[status][size]去dp。
还有一种用变进制：
假设ACGT的总数分别为num[0],num[1],num[2],num[3]
那么对于ACGT的数量分别为ABCD的状态可以记录为：
A*(num[1]+1)*(num[2]+1)*(num[3]+1) + B*(num[2]+1)*(num[3]+1)+ C*(num[3]+1) +D
显然末尾D基数为1，次末尾C基数(num[3]+1)，那么D不管怎么变（最多变num[3]）永远影响不到C那个级数（（num[3] + 1 ）* k），那么就能区分变得是哪一位。
代码：
/*变进制*/
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 500 + 5;
const int M = 50 + 5;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 20090717;
int n, m;
int dp[15000][maxn];
int getid(char s){
if(s == 'A') return 0;
if(s == 'C') return 1;
if(s == 'G') return 2;
return 3;
}
struct Aho{
struct state{
int next[4];
int fail, cnt;
}node[maxn];
int size;
queue<int> q; void init(){
size = 0;
newtrie();
while(!q.empty()) q.pop();
} int newtrie(){
memset(node[size].next, 0, sizeof(node[size].next));
node[size].cnt = node[size].fail = 0;
return size++;
} void insert(char *s){
int len = strlen(s);
int now = 0;
for(int i = 0; i < len; i++){
int c = getid(s[i]);
if(node[now].next[c] == 0){
node[now].next[c] = newtrie();
}
now = node[now].next[c];
}
node[now].cnt++;
} void build(){
node[0].fail = -1;
q.push(0); while(!q.empty()){
int u = q.front();
q.pop();
if(node[node[u].fail].cnt && u) node[u].cnt += node[node[u].fail].cnt;
for(int i = 0; i < 4; i++){
if(!node[u].next[i]){
if(u == 0)
node[u].next[i] = 0;
else
node[u].next[i] = node[node[u].fail].next[i];
}
else{
if(u == 0) node[node[u].next[i]].fail = 0;
else{
int v = node[u].fail;
while(v != -1){
if(node[v].next[i]){
node[node[u].next[i]].fail = node[v].next[i];
break;
}
v = node[v].fail;
}
if(v == -1) node[node[u].next[i]].fail = 0;
}
q.push(node[u].next[i]);
}
}
}
} void query(char *s){
int ans = 0;
int len = strlen(s);
int num[4] = {0};
for(int i = 0; i < len; i++){
num[getid(s[i])]++;
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
int fac[4];
fac[0] = (num[1] + 1) * (num[2] + 1) * (num[3] + 1);
fac[1] = (num[2] + 1) * (num[3] + 1);
fac[2] = (num[3] + 1);
fac[3] = 1;
for(int i = 0; i <= num[0]; i++){
for(int j = 0; j <= num[1]; j++){
for(int k = 0; k <= num[2]; k++){
for(int l = 0; l <= num[3]; l++){
int id = i * fac[0] + j * fac[1] + k * fac[2] + l;
for(int g = 0; g < size; g++){
if(dp[id][g] == -1) continue;
for(int h = 0; h < 4; h++){
int nex;
if(h == 0 && i == num[0]) continue;
if(h == 1 && j == num[1]) continue;
if(h == 2 && k == num[2]) continue;
if(h == 3 && l == num[3]) continue;
nex = id + fac[h];
int add = node[node[g].next[h]].cnt;
if(dp[nex][node[g].next[h]] < dp[id][g] + add){
dp[nex][node[g].next[h]] = dp[id][g] + add;
if(i + j + k + l + 1 == len) ans = max(ans , dp[nex][node[g].next[h]]);
}
}
}
}
}
}
}
printf("%d\n", ans);
} }ac;
char s[45];
int main(){
int ca = 1;
while(~scanf("%d", &n) && n){
ac.init();
for(int i = 0; i < n; i++){
scanf("%s", s);
ac.insert(s);
}
ac.build();
scanf("%s", s);
printf("Case %d: ", ca++);
ac.query(s);
}
return 0;
}
/*Hash*/
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 500 + 5;
const int M = 50 + 5;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 20090717;
int n, m;
int dp[15000][maxn];
int ha[42][42][42][42];
int getid(char s){
if(s == 'A') return 0;
if(s == 'C') return 1;
if(s == 'G') return 2;
return 3;
}
struct Aho{
struct state{
int next[4];
int fail, cnt;
}node[maxn];
int size;
queue<int> q; void init(){
size = 0;
newtrie();
while(!q.empty()) q.pop();
} int newtrie(){
memset(node[size].next, 0, sizeof(node[size].next));
node[size].cnt = node[size].fail = 0;
return size++;
} void insert(char *s){
int len = strlen(s);
int now = 0;
for(int i = 0; i < len; i++){
int c = getid(s[i]);
if(node[now].next[c] == 0){
node[now].next[c] = newtrie();
}
now = node[now].next[c];
}
node[now].cnt++;
} void build(){
node[0].fail = -1;
q.push(0); while(!q.empty()){
int u = q.front();
q.pop();
if(node[node[u].fail].cnt && u) node[u].cnt += node[node[u].fail].cnt; //attention
for(int i = 0; i < 4; i++){
if(!node[u].next[i]){
if(u == 0)
node[u].next[i] = 0;
else
node[u].next[i] = node[node[u].fail].next[i];
}
else{
if(u == 0) node[node[u].next[i]].fail = 0;
else{
int v = node[u].fail;
while(v != -1){
if(node[v].next[i]){
node[node[u].next[i]].fail = node[v].next[i];
break;
}
v = node[v].fail;
}
if(v == -1) node[node[u].next[i]].fail = 0;
}
q.push(node[u].next[i]);
}
}
}
} void query(char *s){
int ans = 0;
int len = strlen(s);
int tot = 0;
int num[4] = {0};
for(int i = 0; i < len; i++){
num[getid(s[i])]++;
}
for(int i = 0; i <= num[0]; i++){
for(int j = 0; j <= num[1]; j++){
for(int k = 0; k <= num[2]; k++){
for(int l = 0; l <= num[3]; l++){
ha[i][j][k][l] = tot;
for(int g = 0; g < size; g++){
dp[tot][g] = -1;
}
tot++;
}
}
}
}
for(int i = 0; i <= num[0]; i++){
for(int j = 0; j <= num[1]; j++){
for(int k = 0; k <= num[2]; k++){
for(int l = 0; l <= num[3]; l++){ }
}
}
}
dp[0][0] = 0;
for(int i = 0; i <= num[0]; i++){
for(int j = 0; j <= num[1]; j++){
for(int k = 0; k <= num[2]; k++){
for(int l = 0; l <= num[3]; l++){
int id = ha[i][j][k][l];
for(int g = 0; g < size; g++){
if(dp[id][g] == -1) continue;
for(int h = 0; h < 4; h++){
int nex;
if(h == 0 && i == num[0]) continue;
if(h == 1 && j == num[1]) continue;
if(h == 2 && k == num[2]) continue;
if(h == 3 && l == num[3]) continue;
if(h == 0) nex = ha[i + 1][j][k][l];
if(h == 1) nex = ha[i][j + 1][k][l];
if(h == 2) nex = ha[i][j][k + 1][l];
if(h == 3) nex = ha[i][j][k][l + 1];
int add = node[node[g].next[h]].cnt;
if(dp[nex][node[g].next[h]] < dp[id][g] + add){
dp[nex][node[g].next[h]] = dp[id][g] + add;
if(i + j + k + l + 1 == len) ans = max(ans , dp[nex][node[g].next[h]]);
}
}
}
}
}
}
}
printf("%d\n", ans);
} }ac;
char s[45];
int main(){
int ca = 1;
while(~scanf("%d", &n) && n){
ac.init();
for(int i = 0; i < n; i++){
scanf("%s", s);
ac.insert(s);
}
ac.build();
scanf("%s", s);
printf("Case %d: ", ca++);
ac.query(s);
}
return 0;
}
最新文章
- Android中webView和网页的交互
- 面向小白的JS笔记 - #Codecademy#学习笔记
- 机器人与机器人仿真技术(zz)
- 3DTouch
- 路径正确下，Eclipse读取txt文件仍失败
- javascript之JSON小案例，实现添加数据与清楚数据
- 【Python 01】Python可以做什么
- Ceph Luminous版本创建OSD无法激活问题
- ArcPy中mapping常见函数及用法1
- for循环将字典添加到列表中出现覆盖前面数据的问题
- ArcFace 2.0 Demo [C++]
- （Gorails视频）使用推广链接（params[:ref]），增加注册用户！
- FFmpeg简易播放器的实现-音视频播放
- scala编程第16章学习笔记（2）
- 数据库日志文件——数据库“xxx”的事务日志已满，原因为“LOG_BACKUP”
- springMvc的执行流程(源码分析)
- 自己创建js文件
- asp.net 初级程序员面试题【待续】
- Yii2.0 新建项目通用准备工作
- Ceph配置文件查看修改方式
热门文章
- DSL是什么？Elasticsearch的Query DSL又是什么？
- Python爬虫：数据分析小能手：JSON库的用法
- 笔记 | 吴恩达新书《Machine Learning Yearning》
- charles安装使用乱码连手机等问题解决方案
- all header field names in both HTTP requests and HTTP responses are case-insensitive.
- 算法总结篇---字典树（Trie）
- cdq分治 笔记
- WeCenter (最新版) 前台RCE漏洞 （2020-02-22）
- Web漏洞扫描-Burp Suite
- 6. Linux输入输出重定向