1651. Shortest Subchain

待我称王封你为后i 2022-01-05 15:41 137阅读 0赞

## 1651. Shortest Subchain ##

Time limit: 1.0 second Memory limit: 64 MB

![Problem illustration][]

A chain   *p*  is given in a directed graph without loops or multiple edges. It is required to specify its subchain   *q*  such that

*  the initial and final vertices of the chains *p* and *q* coincide;
 *  the edges in the chain *q* are in the same order as in the chain *p*;
 *  the chain *q* has the minimal possible number of edges under the given conditions.

### Input ###

The chain   *p*  is given by the list of its vertices. The first line contains the number   *n*  of vertices in the list, 2 ≤   *n*  ≤ 100000 (thus, the length of the chain is   *n*−1). The following lines contain   *n*  numbers of vertices (they are integers in the range from 1 to 10000). The numbers are separated by spaces or linebreaks. No two successive vertices in the list coincide.

### Output ###

Output the vertices of the chain   *q*  by giving their numbers separated by a space. Chain   *q*  may consist of single a vertex.

### Sample ###

<table style="border:1px solid #000000;border-collapse:collapse;"> 
 <tbody> 
  <tr> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">input</th> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">output</th> 
  </tr> 
  <tr> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>9
1 2 7 3 2
8 4 8 5
</pre> </td> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>1 2 8 5
</pre> </td> 
  </tr> 
 </tbody> 
</table>

**Problem Author: **Vladimir Yakovlev (idea by Magaz Asanov) **Problem Source: **NEERC 2008, Eastern subregion quarterfinals

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

图论中的dp，路径更新

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<string>
     5 #include<vector>
     6 #include<algorithm>
     7 #include<stack>
     8 using namespace std;
     9 int used[100001];//表示点被用时所在的位置
    10 int dp[100001];//求最短路径数组
    11 int base[100001];//输入原始数据
    12 int path[100001];//记录选择的点所在的位置
    13 int n,i,j,k;
    14 void  findpath(int x)//输出路径
    15   {
    16       if(x==-1)
    17       return;
    18       cout<<base[x]<<' ';
    19       findpath(path[x]);
    20   }
    21 int main()
    22 {
    23     cin>>n;
    24     for(i=1;i<=n;i++)
    25      cin>>base[i];
    26     memset(used,-1,sizeof(used));
    27     memset(path,-1,sizeof(path));
    28     used[base[n]]=n;
    29     dp[n]=0;
    30     for(i=n-1;i>=1;i--)
    31      {
    32          if(used[base[i]]==-1)//没有用时就选择
    33           {
    34               dp[i]=dp[i+1]+1;
    35               used[base[i]]=i;
    36               path[i]=i+1;
    37           }
    38           else
    39             {
    40                 if(dp[used[base[i]]]>=dp[i+1]+1)//用过以后比较、更新
    41                {
    42                  dp[i]=dp[i+1]+1;
    43                  path[i]=i+1;
    44                  used[base[i]]=i;//点更新到最优位置
    45                }
    46              else
    47               {
    48                   dp[i]=dp[used[base[i]]];
    49                   path[i]=path[used[base[i]]];//路径更新到最优位置
    50               }
    51             }
    52      }
    53      //cout<<dp[1]<<endl;
    54      findpath(1);
    55      cout<<endl;
    56      return 0;
    57 }

转载于:https://www.cnblogs.com/sdau--codeants/p/3259005.html

[Problem illustration]: /images/20211228/7876190d3b504b5b9d513b862123edca.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/6a2c2e3078a5488ea80bddab77140ff6.png