电路布线
【问题描述】
在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连,如图所示。
其中,π(i),1<=i<=n是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1<=i π(j)。
在制作电路板时,要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。你的任务是要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,就是确定导线集Nets={ i,π(i),1<=i<=n}的最大不相交子集。
【输入形式】
输入文件第一行为整数n;第二行为用一个空格隔开的n个整数,表示π(i)。
【输出形式】
输出文件第一行为最多的连线数m,第2行到第m+1行输出这m条连线(i,π(i))。
【输入样例】
10
1 8
2 7
3 4
4 2
5 5
6 1
7 9
8 3
9 10
10 6
【输出样例】
4
思路如下:
比较基础的动态规划问题,设a[i][j]为上端接线柱i与下端接线柱j前的最大不相交子集,则:
- 若i与j不相连,则i与j前的最大不想交子集等于i与j - 1前或i - 1与j前的最大不相交子集的最大值,即a[i][j] = max(a[i][j - 1], a[i - 1][j])
- 若i与j相连,则i与j前的最大不想交子集等于i - 1与j - 1前的最大不想交子集加1,即a[i][j] = a[i - 1][j - 1] + 1
=======================签 名 档=======================
原文地址(我的博客):http://lanfei.sinaapp.com/2012/06/1332.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
acm图论.ppt————电子版_ppt版
动态规划——北京大学暑期课《ACM/ICPC竞赛训练》
ACM 模版ACM 模版ACM 模版ACM 模版
本次课程论文,针对ACM比赛中的经典算法,动态规划,进行了详细的讲述,并以ZOJ和POJ上的经典题目为例,讲述了动态规划算法的应用。
12个ACM动态规划经典题 习题+分析+程序 (转载)
ACM中的动态规划中的状态压缩问题,有讲解和例题。
ACM算法总结大全:基本算法、图算法、数据结构、简单搜索、动态规划、数学、计算几何学等等。
这个ppt主要介绍蛮力搜索的相关内容,这是我竞赛培训的资料,欢迎大家来下载
acm 动态规划 必做50题目
动态规划---做acm的人都知道,很难入门,本资源提供入门窗口
ACM icpc 动态规划 DP专题
acm 动态规划 经典题分析 acm 动态规划 经典题分析 acm 动态规划 经典题分析
acm动态规划经典题,有助于增加对动态规划的理解与应用
acm,动态规划类问题分析,并附有这些问题的详细代码
。
。
acm课件3 动态规划acm课件3 动态规划acm课件3 动态规划acm课件3 动态规划
ACM 编程 算法 之动态规划 课件讲义
都说动态规划题难做,不好找到着手点,所以我总结了杭电的动态规划题目,供acmers学习讨论,共同提高。题目还是比较全面的,有兴趣的同学可以尝试做一做