算法竞赛入门经典(第二版)3-11换低挡装置UVA-1588

这题想了好久啊!!!还各种小细节出错,我太菜了,要更加努力才行

这回要把解题思路写一写,不然估计过几天就忘了

解题思路:

长条固定,移动短条去匹配长条,有三种情况

第一种,在短条在长条范围内移动匹配

算法竞赛入门经典(第二版)3-11换低挡装置UVA-1588

 

 

第二种,短条在长条的左边移动匹配

算法竞赛入门经典(第二版)3-11换低挡装置UVA-1588

 

第三种,短条在长条右边,与左边的情况同理,右移到0与5相等的位置停止匹配

算法竞赛入门经典(第二版)3-11换低挡装置UVA-1588

 

实现代码

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#define maxn 100

    int match(int b1[maxn],int b2[maxn],int len1,int len2) 
    {
//    int len1=length1,len2=length2;
    int min=len1+len2,flag=0;
    for(int k=0;k<=len2-len1;k++)//短串在长串内的情况
    {
        int t=0;
        for(;t<len1;t++)//从左到右,短串移动匹配 
        {
            //printf("b1[%d]=%d b2[%d]=%d\n",t,b1[t],t+k,b2[t+k]);
            if(b1[t]+b2[t+k]>3)
            {
                break;
            }
        }
        if(t==len1){flag =1;break;}
                        
    } 
    if(flag==1) {min=len2;return (min);}    
    
    else
{            
    int r=1;    
    for(;r<len1;r++)//短串在左边,向左移动的情况 
    {
        int s=0;
        for(;s<len1-r;s++)//逐个匹配 
        {
            if(b1[s+r]+b2[s]>3){break;}        
        }
        if(s==len1-r){flag=1;break;}        
    }
    if(flag==1) {min=len2+r;}
        
    int n=1;flag=0;
    for(;n<len1;n++)//短串在右边的,向右移动情况
    {
    int m=len1-1;
    for(;m>=n;m--)//逐个匹配 
    {
        //printf("b1[%d]=%d b2[%d]=%d\n",m-n,b1[m-n],m-len1+len2,b2[m]);
        if(b1[m-n]+b2[m-len1+len2]>3){break;}
        
        }
        if(m<n){flag=1;break;}    
    } 

     if(flag==1){min=len2+n>min?min:len2+n ;return min;}
     else{return min;}
                     
}    
    }    
    
int main()
{
    char a1[maxn],a2[maxn];
    int c1[maxn]={0},c2[maxn]={0};
    gets(a1);
    gets(a2);
    int length1=strlen(a1);
    int length2=strlen(a2);
    
    for(int i=0;i<length1;i++)
    {
        c1[i]=a1[i]-48;//'0'的ASCII码=48
    }    

    for(int j =0;j<length2;j++)
    {
        c2[j]=a2[j]-48;
    }
    int num=length1<=length2?match(c1,c2,length1,length2):match(c2,c1,length2,length1);
    printf("Min_length=%d",num);
}

https://vjudge.net/problem/UVA-1588

 

上一篇:Navicat 连接VMware中Ubuntu 下的mysql5.7遇到的坑


下一篇:BeautifulSoup爬网页图片