#include#include#include#include#" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

poj 1699 Best Sequence

系統 2105 0

http://poj.org/problem?id=1699

題目大意:

給你n個字符串 可以讓他們任意首尾合并相連

求包含所以字符串的最短總字符串長度

注意:

只能首尾合并相連??像 ACTG 和 CT 是不可以的

思路:

求出所以成對字符串合并會增加多少長度 并記錄在表中

然后Dfs搜索就可以啦 剪枝效果更好

代碼及其注釋:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<algorithm>

#include<set>



using namespace std;



const int N=11;

char s[N][N*2];

int l[N];

int addl[N][N];

bool had[N];

int ans, n;

void Findaddl(int I,int J)

{

    int w,i,j;

    for(w=max(0,l[I]-l[J]);w<l[I];++w)

    {



       for(i=w,j=0;j<l[J]&&i<l[I];++j,++i)

       {

           if(s[I][i]!=s[J][j])

           break;

       }

       if(j==l[J]||i==l[I])

       break;

    }

    if(j==l[J])

    addl[I][J]=0;

    else

    addl[I][J]=w+l[J]-l[I];

}

void Dfs(int sum,int Len,int pre)

{

    for(int i=0;i<n;++i)

    {

        if(!had[i])

        {

            had[i]=true;

            if(sum==n)

            {

                ans=min(ans,Len+addl[pre][i]);//枚舉最小 答案

            }

            else if(Len+addl[pre][i]<ans)//剪枝

            {

                Dfs(sum+1,Len+addl[pre][i],i);

            }

            had[i]=false;

        }

    }

}

int main()

{



   int T;

   scanf("%d",&T);

   while(T--)

   {

       scanf("%d",&n);

       getchar();

       ans=0;

       for(int i=0;i<n;++i)

       {

           gets(s[i]);

           l[i]=strlen(s[i]);//求長度

           ans+=l[i];//記錄長度和 這個和是最大長度可能

       }

       for(int i=0;i<n;++i)

       {

           for(int j=0;j<n;++j)

           {

               if(i!=j)

               Findaddl(i,j);//求i 和 j 首尾合并增加多少長度

           }

       }

       memset(had,false,sizeof(had));

       for(int i=0;i<n;++i)

       {

           had[i]=true;

           Dfs(2,l[i],i);//深搜

           had[i]=false;

       }

       printf("%d\n",ans);

   }

   return 0;

}


    

?

poj 1699 Best Sequence


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日韩美女va在线毛片免费知 | 亚洲国产成人久久综合一区77 | 大学生久久香蕉国产线看观看 | 福利视频一区二区 | 手机看片高清国产日韩片 | 国产精品久久久久免费 | 成人免费视频国产 | 国产一区二区三区免费在线观看 | 国产全黄一级毛片 | 国产精品9999久久久久仙踪林 | 久久国产影视免费精品 | 我要看一级毛片 | 国产精品久久久久9999 | 欧美日韩视频精品一区二区 | 欧美一级毛片aaaaa | 色婷婷久久综合中文久久一本 | 国产精品1区2区3区在线播放 | 青青青国产精品一区二区 | 99热国产在线 | 狠狠色丁婷婷综合久久 | 99久久一香蕉国产线看观看 | 四虎成人永久地址 | 日本二级毛片免费 | 男女一级免费视频 | 2020年国产高中毛片在线视频 | 中文字幕日韩精品亚洲七区 | 一本伊大人香蕉高清在线观看 | 久久国产网 | 天天色天天操综合网 | 日韩色在线| 91国内精品久久久久影院优播 | 九九热这里只有国产精品 | 99这里| 久久国产亚洲高清观看5388 | 特黄特色大片免费播放器999 | 国产不卡免费 | 国精品在亚洲_欧美 | 成人久久网站 | 中文字幕一区在线观看视频 | 色片在线观看 | 夜夜躁狠狠躁日日躁2021 |