uva 1588 Kickdown

本文主要是介绍uva 1588 Kickdown，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
A research laboratory of a world-leading automobile company has received an order to create a special transmission mechanism, which allows for incredibly efficient kickdown — an operation of switching to lower gear. After several months of research engineers found that the most efficient solution requires special gears with teeth and cavities placed non-uniformly. They calculated the optimal flanks of the gears. Now they want to perform some experiments to prove their findings.
The first phase of the experiment is done with planar toothed sections, not round-shaped gears. A section of length n consists of n units. The unit is either a cavity of height h or a tooth of height 2h. Two sections are required for the experiment: one to emulate master gear (with teeth at the bottom) and one for the driven gear (with teeth at the top).

There is a long stripe of width 3h in the laboratory and its length is enough for cutting two engaged sections together. The sections are irregular but they may still be put together if shifted along each other.

The stripe is made of an expensive alloy, so the engineers want to use as little of it as possible. You need to find the minimal length of the stripe which is enough for cutting both sections simultaneously.
Input
The input file contains several test cases, each of them as described below. There are two lines in the input, each contains a string to describe a section. The first line describes master section (teeth at the bottom) and the second line describes driven section (teeth at the top). Each character in a string represents one section unit — 1 for a cavity and 2 for a tooth. The sections
can not be flipped or rotated. Each string is non-empty and its length does not exceed 100.
Output
For each test case, write to the output a line containing a single integer number — the minimal length
of the stripe required to cut off given sections.
Sample Input
2112112112
2212112
12121212
21212121
2211221122
21212
Sample Output
10
8
15

中文：

给你两个长条，每个长条上面都有深度为1的凹槽。如上面的图所示，现在让你把这两个长条放在一个高度为3的容器当中，问你最短的容器长度是多少。

注意，长条不能改变方向，也就是不能头变尾，尾变头。

代码：

#include<bits/stdc++.h>
using namespace std;
char s1[150],s2[150];bool com(char c1,char c2)
{if(c1=='2'&&c2=='2')return false;return true;
}int solve(int len1,int len2)
{int ans=INT_MAX;for(int i=1;i<=len2;i++){int flag=0,tmp;if(i<=len1){for(int j=1;j<=i;j++){if(!com(s1[len1-j+1],s2[i-j+1])){flag=1;break;}}if(!flag){tmp=len1-i+len2;ans=min(ans,tmp);}}else{for(int j=1;j<=len1;j++){if(!com(s1[len1-j+1],s2[i-j+1])){flag=1;break;}}if(!flag){return len2;}}}return ans;
}int main ()
{ios::sync_with_stdio(false);while(cin>>s1+1>>s2+1){int len1=strlen(s1+1);int len2=strlen(s2+1);int ans=len1+len2;//211 221ans=min(solve(len1,len2),ans);//cout<<ans<<endl;swap(s1,s2);swap(len1,len2);ans=min(solve(len1,len2),ans);cout<<ans<<endl;}return 0;
}

解答：

紫书上的训练题，这题很简单，模拟即可，数据也很小。但是注意长条只能按照给定的首位位置来计算和判断，不能把一个长条扭过来计算。

这篇关于uva 1588 Kickdown的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---