Paste_Image.png
include <iostream>
using namespace std;
int max(int x, int y){
return x>y?x:y;
}
void MNS(int c[], int n, int **size){
//根据心中那张表初始化第一行
for(int j = 0; j < c[1]; j++){
size[1][j] = 0;
}
for(int j = c[1]; j <= n; j++){
size[1][j] = 1;
}
//然后从第二行开始每一行填充那张表
for(int i = 2; i <= n; i++){
//要是j<c[i]
for(int j = 0; j < c[i]; j++){
size[i][j] = size[i-1][j];
}
//要是j>=c[i]
for(int j = c[i]; j <= n; j++){
size[i][j] = max(size[i-1][j], size[i-1][c[i]-1]+1);
}
}
size[n][n] = max(size[n-1][n], size[n-1][c[n]-1]+1);
}
void TraceBack(int c[], int **size, int n, int net[], int &m){
int j = n;
m = 0;
for(int i = n; i > 1; i--){
if(size[i][j] != size[i-1][j]){
net[m++] = i;
j = c[i] - 1;
}
}
//处理i为1的情况【不能放一块处理的原因是那张表下面没值了】
if(j >= c[1]){
net[m++] = 1;
}
}
int main(){
//首先输入一个接好的线【便于测试】
//int c[] = {0,8,7,4,2,5,1,9,3,10,6};
cout<<"输入一共有几个接线柱:"<<endl;
int n;
cin>>n;
cout<<"依次输入这个n个接线柱连着哪一个,空格隔开:"<<endl;
int c [n+1];
c[0] = 0;
for(int i = 1; i<=n ; i++){
cin>>c[i];
}
//开辟一个二维数组存入每种情况的最大值
int **size = new int* [n+1];
for(int i = 0; i <= n; i++){
size[i] = new int[n+1];
}
MNS(c, n, size);
cout<<"最大不相交连线的数目为:"<<size[n][n]<<endl;
int net[n], m;
TraceBack(c, size, n, net, m);
cout<<"最大不相交交连线为:"<<endl;
for(int i = m-1; i >= 0; i--){
cout<<"["<<net[i]<<","<<c[net[i]]<<"]"<<" ";
}
}
