hdu 1560 DNA sequence(IDA*)

 

 

HDU 1560DNA sequence

 

HDU 1005 Number Sequence(矩阵),hdu1005

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 177761    Accepted Submission(s): 44124

Problem Description A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).  

 

Input The input consists of multiple test cases. Each test case contains
3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <=
n <= 100,000,000). Three zeros signal the end of input and this test
case is not to be processed.  

 

Output For each test case, print the value of f(n) on a single line.  

 

Sample Input 1 1 3 1 2 10 0 0 0  

 

Sample Output 2 5  

 

Author CHEN, Shunbao  

 

Source ZJCPC2004  

 

Recommend   JGShining   |   We have carefully selected several similar
problems for you:  1008 1004 1021 1019 1002     
那道题要求推三个近乎于斐波那契矩阵的矩阵。 比较好推
图片 1

 

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int MAXN=1001;
 6 inline void read(int &n){char c='+';bool flag=0;n=0;    
 7 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();    
 8 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;}
 9 struct matrix
10 {
11     int m[3][3];matrix(){memset(m,0,sizeof(m));}
12 };
13 matrix ma;
14 int limit=2;
15 const int mod=7;
16 matrix mul(matrix a,matrix b)
17 {
18     matrix c;
19     for(int k=0;k<limit;k++)
20         for(int i=0;i<limit;i++)
21             for(int j=0;j<limit;j++)
22                 c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j]))%mod;
23     return c;
24 }
25 matrix fast_martix_pow(matrix ma,int p)
26 {
27     matrix bg;
28     bg.m[0][0]=1;bg.m[1][1]=1;
29     bg.m[0][1]=0;bg.m[1][0]=0;
30     /*for(int i=0;i<limit;i++)
31     {
32         for(int j=0;j<limit;j++)
33             cout<<bg.m[i][j]<<" ";
34         cout<<endl;
35     }*/
36         
37     while(p)
38     {
39         if(p&1)    bg=mul(bg,ma);
40         ma=mul(ma,ma);
41         p>>=1;
42     }
43     return bg;
44 }
45 int main()
46 {
47     int a,b,n;
48     while(scanf("%d%d%d",&a,&b,&n)&&(a!=0&&b!=0&&n!=0))
49     {
50         ma.m[0][0]=a;ma.m[0][1]=b;
51         ma.m[1][0]=1;ma.m[1][1]=0;
52         if(n<3)
53         {
54             printf("1n");
55             continue;
56         }
57         matrix ans=fast_martix_pow(ma,n-2);
58         printf("%dn",(ans.m[0][1]+ans.m[0][0])%mod);
59     }
60     return 0;
61 }

 

1005 Number Sequence(矩阵),hdu1005 Time
Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K
(Java/Others) Total Submission(s): 177761Accepted Submission(s):
44…

DNA sequence

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K
(Java/Others) Total Submission(s): 1505 Accepted Submission(s): 730

Problem Description The twenty-first century is a biology-technology
developing century. We know that a gene is made of DNA. The nucleotide
bases from which DNA is built are A(adenine), C(cytosine), G(guanine),
and T(thymine). Finding the longest common subsequence between
DNA/Protein sequences is one of the basic problems in modern
computational molecular biology. But this problem is a little different.
Given several DNA sequences, you are asked to make a shortest sequence
from them so that each of the given sequence is the subsequence of it.

For example, given “ACGT”,”ATGC”,”CGTT” and “CAGT”, you can make a
sequence in the following way. It is the shortest but may be not the
only one.

图片 2

Input The first line is the test case number t. Then t test cases
follow. In each case, the first line is an integer n ( 1<=n<=8 )
represents number of the DNA sequences. The following k lines contain
the k sequences, one per line. Assuming that the length of any sequence
is between 1 and 5.
Output For each test case, print a line containing the length of the
shortest sequence that can be made from these sequences.
Sample Input

1
4
ACGT
ATGC
CGTT
CAGT

Sample Output

8

Author LL
Source HDU 2006-12 Programming Contest
Recommend LL | We have carefully selected several similar problems for
you: 1667 1043 1813 1226 1401
难题概况:给n个类别,找到三个饱含全体给出系列的最短长度并出口。
解题思路:采纳gei_h()获得当前地方下最长的未相称的长度。在实行深度寻找。每个串的长短不超越5,最五只有8个体系,所以IDA不超过四十一次。
详细代码。

#include 
#include 
#include 
#include 

using namespace std;

int n;
char ch[10][10];
int len[10],want;
char dir[10]= {'A','C','G','T'};
int wei[10];//记录第i个序列正在使用第几个位置

int get_h()
{
    int t=0;
    for (int i=1; i<=n; i++)
    {
        t=max(t,len[i]-wei[i]);//得到当前情况下最长的未被匹配的长度
    }
    return t;
}

int IDA(int dep)
{
    if(dep+get_h()>want)//当前长度+估测的长度比我想要的还大的话,就不必继续搜索
    {//cout<<Max)
                Max=len[i];
        }
        memset(wei,0,sizeof(wei));
        want=Max;//从最长序列开始查找
        while (1)
        {
            if (IDA(0))
            {
                break;
            }
            want++;
        }
        printf ("%dn",want);
    }
    return 0;
}
<

 

1560 DNA sequence(IDA*) DNA sequence Time
Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K
(Java/Others) Total Submission(s): 1505 Accepted Submission(s):
730…

DNA sequence

Time Limit : 15000/5000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 8 Accepted Submission(s) : 1

Problem Description The twenty-first century is a biology-technology
developing century. We know that a gene is made of DNA. The nucleotide
bases from which DNA is built are A(adenine), C(cytosine), G(guanine),
and T(thymine). Finding the longest common subsequence between
DNA/Protein sequences is one of the basic problems in modern
computational molecular biology. But this problem is a little different.
Given several DNA sequences, you are asked to make a shortest sequence
from them so that each of the given sequence is the subsequence of it.

For example, given ACGT,ATGC,CGTT and CAGT, you can make a sequence in
the following way. It is the shortest but may be not the only one.

图片 3

Input The first line is the test case number t. Then t test cases
follow. In each case, the first line is an integer n ( 1<=n<=8 )
represents number of the DNA sequences. The following k lines contain
the k sequences, one per line. Assuming that the length of any sequence
is between 1 and 5.
Output For each test case, print a line containing the length of the
shortest sequence that can be made from these sequences.
Sample Input

1
4
ACGT
ATGC
CGTT
CAGT

Sample Output

8

Author LL
Source HDU 2006-12 Programming Contest

 

 

找到最短的DNA种类 其子连串包蕴题意所给的DNA

IDA* 价值评估函数为最长剩余DNA数量

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<30
#define LL long long
#define maxn 1<<24
using namespace std;
char str[10][10];//保存DNA
int l[10];
int t,n;
int tlen;
bool flag;

int get_h(int * a)  //估价函数
{
    int ans=0;
    for(int i=0; ilen) return ;//预估值小于最优估计值

    if(len==0)  //找到序列
    {
        flag=true ;
        return  ;
    }

    bool vis[10];
    memset(vis,false ,sizeof(vis));
    for(int i=0; i  

1560DNA sequence DNA sequence Time Limit :
15000/5000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) Total
Submission(s) : 8 Accepted Submission(s) : 1 Problem Descrip…

相关文章