首页 > 代码库 > HDOJ 1560 DNA sequence 状压dp 或 IDA*

HDOJ 1560 DNA sequence 状压dp 或 IDA*

2024-07-16 05:52:34   215人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1560

题意：

给不超过8个子串，每个子串最多5位，且都只包含ATCG，求最短的母串长度。

分析：

又是上个月写的，所以有点忘了。。正解是IDA*。然后可以状压dp，记忆化搜索。dp[i]，i用6进制表示，每位表示对应的子串匹配那么多长度所需要的最短母串长度。比如两个子串，13=2*6^1+1*6^0，dp[13]就表示第一个串匹配了第一位，第二个串匹配前两位所需要的最短母串长度。

状态讲完了，不过实际上程序里是倒着做的，也就是从末尾开始匹配。转移就是枚举母串最后一位分别为ATCG，然后如果子串未匹配的最后一位相同那就匹配上了，压缩出新的六进制数继续搜下去，递归到0。dp[i] = min(dp[j] + 1)。

然后数组比较大，在网上看到一个hash标记的方法，这样就不用总是memset，速度快了1s+。

额。。找到了当时写在文档里的一点点题解，比现在回顾写得清晰一点吧。。

<style></style><style></style>

正解是IDA*，数据范围小可以用状压，记忆化搜索。dp[i]=min(dp[j])+1,i用六进制，每一位表示为每个子序列匹配了(0-5)的长度，母序列所需要的最小长度，转移时就是删掉ATCG中一个，判断每个子序列最后匹配的那一位是否相同(相同删掉，可能会疑惑如果不是匹配母串的当前这位怎么能也删掉，实际上贪心地看，越早匹配掉越好，就是比如dp[3 * 6 + 2]是优于(可能小于) dp[3 * 6 + 3]的)，由此得到子状态j的值

 

 

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 int n, cas; 6 int dp[6*6*6*6*6*6*6*6 + 100], 7     ha[6*6*6*6*6*6*6*6 + 100]; 8 char str[10][10]; 9 char ch[4] = {‘A‘, ‘T‘, ‘C‘, ‘G‘};10 int min(int a, int b)11 {12     if (a < b) return a; else return b;13 }14 void F(int x)15 {16     if (ha[x] == cas) return;17     int xx = x, p[10], op[10];18     for (int i = n - 1; i >= 0; i--)19     {20         op[i] = p[i] = xx % 6;            //解码21         xx /= 6;22     }23     for (int i = 0; i < 4; i++)24     {25         for (int j = 0; j < n; j++)26             if (p[j] > 0 && str[j][p[j] - 1] == ch[i]) p[j] --;    //匹配上目前枚举的字符27         int sum = 0;28         for (int j = 0; j < n; j++)29             sum = sum * 6 + p[j];                    //再压缩编码30         for (int j = 0; j < n; j++)31             p[j] = op[j];32         if (sum == x) continue;33         F(sum);                            //递归求解34         //dp[x] = dp[x]==-1? dp[sum]+1: min(dp[x], dp[sum]+1);35         if (ha[x] != cas)36         {37             dp[x] = dp[sum] + 1;38             ha[x] = cas;39         }40         else41         {42             dp[x] = min(dp[sum] + 1, dp[x]);43             //ha[x] = cas;44         }45     }46 }47 int main()48 {49     int T;50     scanf("%d", &T);51     cas = 0;52     memset(ha, -1, sizeof(ha));53     while (T--)54     {55         scanf("%d", &n); getchar();56         //memset(dp, -1, sizeof(dp));57         int sum = 0;58         for (int i = 0; i < n; i++)59         {60             scanf("%s", str[i]);61             sum = sum * 6 + strlen(str[i]);        //压缩编码62         }63         dp[0] = 0;64         F(sum);65         printf("%d\n", dp[sum]);66         cas++;67     }68     return 0;69 }

 


联系
我们