uva1133---Vacation
发布日期:2022-02-02 02:58:12 浏览次数:14 分类:技术文章

本文共 3427 字,大约阅读时间需要 11 分钟。

The Problem

You are planning to take some rest and to go out on vacation, but you really don't know which cities you should visit. So, you ask your parents for help. Your mother says"My son, you MUST visit Paris, Madrid, Lisboa and London. But it's only fun in this order." Then your father says:"Son, if you're planning to travel, go first to Paris, then to Lisboa, then to London and then, at last, go to Madrid. I know what I'm talking about."

Now you're a bit confused, as you didn't expected this situation. You're afraid that you'll hurt your mother if you follow your father's suggestion. But you're also afraid to hurt your father if you follow you mother's suggestion. But it can get worse, because you can hurt both of them if you simply ignore their suggestions!

Thus, you decide that you'll try to follow their suggestions in the better way that you can. So, you realize that the "Paris-Lisboa-London" order is the one which better satisfies both your mother and your father. Afterwards you can say that you could not visit Madrid, even though you would've liked it very much.

If your father have suggested the "London-Paris-Lisboa-Madrid" order, then you would have two orders, "Paris-Lisboa" and "Paris-Madrid", that would better satisfy both of your parent's suggestions. In this case, you could only visit 2 cities.

You want to avoid problems like this one in the future. And what if their travel suggestions were bigger? Probably you would not find the better way very easy. So, you decided to write a program to help you in this task. You'll represent each city by one character, using uppercase letters, lowercase letters, digits and the space. Thus, you can have at most 63 different cities to visit. But it's possible that you'll visit some city more than once.

If you represent Paris with "a", Madrid with "b", Lisboa with "c" and London with "d", then your mother's suggestion would be "abcd" and you father's suggestion would be "acdb" (or "dacb", in the second example).

The program will read two travel sequences and it must answer how many cities you can travel to such that you'll satisfy both of your parents and it's maximum.

The Input

The input will consist on an arbitrary number of city sequence pairs. The end of input occurs when the first  sequence starts with an "#"character (without the quotes). Your program should not process this case. Each travel sequence will be on a line alone and will be formed by legal characters (as defined above).  All travel sequences will appear in a single line and will have at most 100 cities.

The Output

For each sequence pair, you must print the following message in a line alone:

Case #d: you can visit at most K cities.

Where d stands for the test case number (starting from 1) and K is the maximum number of cities you can visit such that you'll satisfy both you father's suggestion and you mother's suggestion.

Sample Inputabcdacdbabcddacb#
Sample OutputCase #1: you can visit at most 3 cities.Case #2: you can visit at most 2 cities. 
题目大意:

一个人想要出去旅游,爸爸给了一个旅游序列,妈妈给了一个旅游序列,他想尽可能满足爸妈的建议,问她最多可以访问多少个城市?

代码实现:

#include
#include
#include
using namespace std;char str1[101];char str2[101];int dp[101][101];int main(){ int ans=0; while(cin>>str1>>str2) { ans++; if(str1[0]=='#') break; memset(dp,0,sizeof(dp)); int len1=strlen(str1); int len2=strlen(str2); for(int i=0;i

转载地址:https://blog.csdn.net/u010368749/article/details/20361419 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:最长公共子序列
下一篇:hdu1080---Human Gene Functions

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月14日 15时57分34秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

如何使用matlab的siso,利用Matlab内建程式SISODesignTool完成系统分析(Matlab61)开启.PDF... 2019-04-21
php 实现 model层,Thinkhphp5控制器调用的Model层的方法总结 2019-04-21
matlab6.0序列号,MFC软件获取USB设备的制造商、产品、序列号 2019-04-21
matlab中多边形滤波器,几种常见空间滤波器MATLAB实现 2019-04-21
matlab fminimax 例子,Matlab应用实例(8)—fminimax 2019-04-21
php://filter利用条件,浅谈php://filter技巧 2019-04-21
mplayer-php,mplayer+smplayer 前后端播放器安装 2019-04-21
oracle昨日时间,。。今日,昨日,上周,本月,本年,按时间统计总金额 2019-04-21
php验证卡号,PHP验证信用卡卡号是否正确函数 2019-04-21
mpvue微信小程序动画_推荐两个微信小程序开发框架 2019-04-21
固态硬盘分为哪几种_零基础玩转固态硬盘 深度排雷 买SSD掌握这些就够了 2019-04-21
调python返回图片_Python异常处理,3个好习惯分享给你 2019-04-21
15拆解_收藏:15款劲芯微芯片无线充产品拆解 2019-04-21
弹出u盘_都说:U盘直接拔出不会丢失文件,“安全弹出”形同虚设,对吗? 2019-04-21
怎么查看elementui版本_2021新年 Vue3.0 + Element UI 尝鲜小记 2019-04-21
adreno630gpu参数_小米8搭载Adreno 630图形处理器 比荣耀play上的GPU Turbo更成熟 2019-04-21
带bitlocker解密的pe_如何在PE下解锁bitlocker 2019-04-21
lj245a引脚功能图_谁找到74254,74LS245芯片引脚的功能和功能图啊? 2019-04-21
sts 创建webservice项目_通过eclipse将Java生成webservice | 学步园 2019-04-21
python数字字符串和数字相加_数字和字符串 2019-04-21