换低挡装置（Kickdown）

桃扇骨 2022-11-24 12:57 53阅读 0赞

给出两个长度分别为n1，n2（n1，n2≤100）且每列高度只为1或2的长条。需要将它们放 入一个高度为3的容器（如图3-8所示），问能够容纳它们的最短容器长度。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]

分析：先固定较长的长条，让短的那根长条从开始往后移，吻合的话就输出，结束。

#include<stdio.h>
    #include<string.h>
    int search(int m,int n,char strip1[],char strip2[])
    { 
        int ans=0,temp=0,ok=1;
        for(int k1=0;k1<=m;k1++)
        { 
      	int ok1=1,k=k1,ok2=1;
      	for(int k2=0;k2<n&&k<m;k2++,k++)
      	{ 
                if((strip1[k]+strip2[k2])>('3'+48))
                { 
        		ok1=0;
        		break;
       	    }
      	}
      	if(ok1)
      	{ 
                if(n+k1<=m)
                { 
        		ans=m;
        		break;
                }
       	    else
       	   { 
                	ans=n+k1;
                    break;
       	   }
            }
        }
        for(int i=n-1;i>=0;i--)
        { 
            ok=1;temp=i;
            for(int j=n-1;j>=n-1-i;j--,temp--)
            { 
       	      if(strip1[temp]+strip2[j]>=100)
       	      { 
                       ok=0;
                       break;
       	      } 
            }
            if(ok)
            { 
       	    ans=(ans>(m+n-i-1)?(m+n-i-1):ans);
                break;
            }
         }
        printf("%d\n",ans);
    }
    int main()
    { 
        char strip1[105],strip2[105];
        memset(strip1,'A',sizeof(strip1));
        memset(strip2,'A',sizeof(strip2));
        while(~scanf("%s%s"),strip1,strip2)
        { 
      	int m=strlen(strip1);
      	int n=strlen(strip2);
      	if(m<n)
      	{ 
                search(n,m,strip2,strip1);
      	}
      	else
      	{ 
                search(m,n,strip1,strip2);
      	}
      	memset(strip1,'A',sizeof(strip1));
            memset(strip2,'A',sizeof(strip2));
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]: /images/20221124/e9632cde33bc4a31868295466c960494.png