電路布線

【問題描述】
在一塊電路板的上、下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線（i，π(i)）將上端接線柱i與下端接線柱π(i)相連，如圖所示。

其中，π(i)，1<=i<=n是{1，2，…，n}的一個(gè)排列。導(dǎo)線（i，π(i)）稱為該電路板上的第i條連線。對于任何1<=i π(j)。

在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。你的任務(wù)是要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，就是確定導(dǎo)線集Nets={ i，π(i)，1<=i<=n}的最大不相交子集。

【輸入形式】
輸入文件第一行為整數(shù)n；第二行為用一個(gè)空格隔開的n個(gè)整數(shù)，表示π(i)。

【輸出形式】
輸出文件第一行為最多的連線數(shù)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

思路如下：

比較基礎(chǔ)的動(dòng)態(tài)規(guī)劃問題，設(shè)a[i][j]為上端接線柱i與下端接線柱j前的最大不相交子集，則：

1. 若i與j不相連，則i與j前的最大不想交子集等于i與j - 1前或i - 1與j前的最大不相交子集的最大值，即a[i][j] = max(a[i][j - 1], a[i - 1][j])
2. 若i與j相連，則i與j前的最大不想交子集等于i - 1與j - 1前的最大不想交子集加1，即a[i][j] = a[i - 1][j - 1] + 1

    #include<stdio.h>

inline int max(int a, int b){
	return a > b ? a : b;
}

int main(){
	int n, i, j;
	int a[100][100], b[100];
	a[0][0] = 0;
	scanf("%d", &n);
	for(i = 0; i < n; ++i){
		int j;
		scanf("%d", &j);
		scanf("%d", &b[j]);
		a[i][0] = 0;
		a[0][i] = 0;
	}
	for(i = 1; i <= n; ++i){
		for(j = 1; j <= n; ++j){
			if(b[i] == j){
				a[i][j] = a[i - 1][j - 1] + 1;
			}else{
				a[i][j] = max(a[i - 1][j], a[i][j - 1]);
			}
		}
	}
	printf("%d\n", a[n][n]);
	return 0;
}
  

=======================簽 名 檔=======================
原文地址（我的博客）： http://www.clanfei.com/2012/06/1332.html
歡迎訪問交流，至于我為什么要多弄一個(gè)博客，因?yàn)槲覠釔矍岸耍瑹釔劬W(wǎng)頁，我更希望有一個(gè)更加自由、真正屬于我自己的小站，或許并不是那么有名氣，但至少能夠讓我為了它而加倍努力。。
=======================簽 名 檔=======================

[ACM]簡單動(dòng)態(tài)規(guī)劃——電路布線