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]]<<"]"<<" ";
} 

}