Kickdown UVA - 1588

这道题把两个拼在一起,不能翻转,我们可以固定一的位置,把二放到一下面,但是不要忘记,第二个的最左端可以在第一个最左端的左边,所以遍历二的左边的可能性实际上(假设一最左边位置为b1,长度n1,二类推)从b1-n2到b1+n1,如果我们把n2取最大100,那不妨假定b1位置就为100,当n2实际没有100时,假设为50,那我们从0到50的位置实际上第一个和第二个并不会接触,这些情况答案大于n1+n2,但是最终答案并不会改变,因为继续遍历必定会遍历到n1+n2,而n1+n2小于之前这些从0到50的这些不存在的情况的答案,所以无所谓。

#include <bits/stdc++.h>
using namespace std;
char first[105], second[105];
int fir[305],sec[105];//注意因为第一段的左100,右100和自己的100都是合法的位置,因为第二段可以放到第一段的最右,当两段均为100时,第一段的起始位置为100,末尾200,加上第二段就300 
int main()
{
	while(scanf("%s", first) != EOF)
	{
		memset(fir, 0, sizeof(fir));
		memset(sec, 0, sizeof(sec));
		int ans = 0x3f3f3f3f;
		scanf("%s", second);
		int fir_cnt = strlen(first);
		int sec_cnt = strlen(second);
		for(int i = 0; i < fir_cnt; i++)
		{
			fir[100 + i] = first[i] - '0';//第一段最左边从100开始,因为从0~99这100个位置可能放置第二段的 
		}
		for(int i = 0; i < sec_cnt; i++)
		{
			sec[i] = second[i] - '0';
		}
		for(int i = 0; i < fir_cnt + 100; i++)//第二段的起始位置 
		{
			bool flag = true;
			for(int j = 0; j < sec_cnt; j++)
			{
				if(fir[i + j] + sec[j] > 3)
				{
					flag = false;
					break;
				}
			}
			if(flag)
			{
				ans = min(ans, max(fir_cnt + 100, i + sec_cnt) - min(i, 100));//取两段最右减去两段最左即得到两段合起来的两端长度 
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

  

 

上一篇:Uva 11059 最大乘积


下一篇:UVA 1218 完美服务 (紫薯系列)(树形dp分类讨论与优化)