因为dp(i,j)=dp(j,i),所以令i>j. dp(i,j)=max(dp(k,j))+1(0<=k<i),若此时dp(i,j)=1则让dp(i,j)=0.(因为无法到达此状态,等于1是因为后来加1了).初始:dp(0,0)=1.answer: max(dp(i,n-1))(0<=i<n).比较难理解的是为什么状态转移时为什么不会出现重复,只要我们每次计算时没有计算重复点,那么之前的计算也不会有(因为是同样的dp计算方式),所以就不会重复.
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
Canada Tour
You have won a contest sponsored by an airline. The prize is a ticket to travel around Canada, beginning in the most western point served by this airline, then traveling only from west to east until you reach the most eastern point served, and then coming back only from east to west until you reach the starting city. No city may be visited more than once, except for the starting city, which must be visited exactly twice (at the beginning and the end of the trip). You are not allowed to use any other airline or any other means of transportation.
Given a list of cities served by the airline and a list of direct flights between pairs of cities, find an itinerary which visits as many cities as possible and satisfies the above conditions beginning with the first city and visiting the last city on the list and returning to the first city.
PROGRAM NAME: tour
INPUT FORMAT
Line 1: | The number N of cities served by the airline and the number V of direct flights that will be listed. N will be a positive integer not larger than 100. V is any positive integer. |
Lines 2..N+1: | Each line contains a name of a city served by the airline. The names are ordered from west to east in the input file. There are no two cities in the same meridian. The name of each city is a string of, at most, 15 digits and/or characters of the Latin alphabet; there are no spaces in the name of a city. |
Lines N+2..N+2+V-1: | Each line contains two names of cities (taken from the supplied list), separated by a single blank space. This pair is connected by a direct, two-way airline flight. |
SAMPLE INPUT (file tour.in)
8 9 Vancouver Yellowknife Edmonton Calgary Winnipeg Toronto Montreal Halifax Vancouver Edmonton Vancouver Calgary Calgary Winnipeg Winnipeg Toronto Toronto Halifax Montreal Halifax Edmonton Montreal Edmonton Yellowknife Edmonton Calgary
OUTPUT FORMAT
Line 1: | The number M of different cities visited in the optimal itinerary. Output 1 if no itinerary is possible. |
SAMPLE OUTPUT (file tour.out)
7
Namely: Vancouver, Edmonton, Montreal, Halifax, Toronto, Winnipeg, Calgary, and Vancouver (but that's not a different city).
USACO Seciton 5.4 Canada Tour(dp)的更多相关文章
-
USACO 5.4 Canada Tour
Canada Tour You have won a contest sponsored by an airline. The prize is a ticket to travel around C ...
-
[洛谷P2747] [USACO5.4]周游加拿大Canada Tour
洛谷题目链接:[USACO5.4]周游加拿大Canada Tour 题目描述 你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票.旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行, ...
-
洛谷 P2747 [USACO5.4]周游加拿大Canada Tour 解题报告
P2747 [USACO5.4]周游加拿大Canada Tour 题目描述 你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票.旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行,直 ...
-
洛谷 P2747 [USACO5.4]周游加拿大Canada Tour
P2747 [USACO5.4]周游加拿大Canada Tour 题目描述 你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票.旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行,直 ...
-
USACO 6.5 Betsy&#39;s Tour (插头dp)
Betsy's TourDon Piele A square township has been divided up into N2 square plots (1 <= N <= 7) ...
-
洛谷P2747周游加拿大Canada Tour [USACO5.4] dp
正解:dp 解题报告: 传送门! 其实这题是我做网络流的时候发现了这题,感觉有点像双倍经验,,,? 但是我还不想写网络流的题解,,,因为网络流24题都还麻油做完,,,想着全做完了再写个总的题解什么的( ...
-
POJ2677 Tour[DP 状态规定]
Tour Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4307 Accepted: 1894 Description ...
-
【USACO 2.2】Subset Sums (DP)
N (1 <= N <= 39),问有多少种把1到N划分为两个集合的方法使得两个集合的和相等. 如果总和为奇数,那么就是0种划分方案.否则用dp做. dp[i][j]表示前 i 个数划分到 ...
-
POJ2677 Tour(DP+双调欧几里得旅行商问题)
Tour Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3929 Accepted: 1761 Description ...
随机推荐
-
QGEditors.WinForms WinForms下使用的部分扩展控件
Nuget: https://www.nuget.org/packages/QGEditors.WinForms/ PM> Install-Package QGEditors.WinForms ...
-
【数据结构】建立和平衡AVL二叉树
一步一步写平衡二叉树(AVL树) 原文地址:http://www.cppblog.com/cxiaojia/archive/2012/08/20/187776.html 我添加了一些内容,以充实整个算 ...
-
MSIL指令集
名称 说明 Add 将两个值相加并将结果推送到计算堆栈上. Add.Ovf 将两个整数相加,执行溢出检查,并且将结果推送到计算堆栈上. Add.Ovf.Un 将两个无符号整数值相加,执行溢出检查,并且 ...
-
webrtc学习———记录二:canvas学习
参考资料: http://bucephalus.org/text/CanvasHandbook/CanvasHandbook.html#getcontext2d https://developer.m ...
-
window.onscroll
http://www.w3help.org/zh-cn/causes/SD9013 1.各浏览器对 document.document.body.document.documentElement 对象 ...
-
(转载)C# 编程 使用可空类型
转载出处为://https://msdn.microsoft.com/zh-cn/library/2cf62fcy(vs.90).aspx#Anchor_1 C#可以为 null 的类型可以表示基础类 ...
-
【Nginx笔记】nginx配置文件具体解释
本文主要对nginx的配置做重点说明,关于nginx的其他基本概念.建议參考官网描写叙述.这里推荐Nginx Beginner's Guide这篇文档.对刚開始学习的人高速认识nginx非常有帮助. ...
-
ssh的public key的使用
1.在客户端Xftp的工具栏tools->Key Generation Parameters 弹出会话窗口,在key type中选择RSA
-
流式大数据计算实践(2)----Hadoop集群和Zookeeper
一.前言 1.上一文搭建好了Hadoop单机模式,这一文继续搭建Hadoop集群 二.搭建Hadoop集群 1.根据上文的流程得到两台单机模式的机器,并保证两台单机模式正常启动,记得第二台机器core ...
-
TortoiseGit为github账号添加SSH keys,解决pull总是提示输入密码的问题
每次同步或者上传代码到githun上的代码库时,需要每次都输入用户名和密码,这时我们设置一下SSH key就可以省去这些麻烦了.若果使用TortoiseGit作为github本地管理工具,Tortoi ...