CodeForces1204C-白红宇

CodeForces1204C

阅读量：5289 次

发布时间：2019-06-14

本文共 1584 字，大约阅读时间需要 5 分钟。

其实我觉得这是一道比较综合的题吧...

这个题可供挖掘的性质很多,比如最短路最长是\(n\)啊,答案序列中的两点之间的距离肯定是\(p\)数组上这两个点的距离啊等等.

其实是在\(p\)数组上进行了一次另类的最短子序列.图的条件其实就是限制了转移,然后再有一个有点意思的地方是\(DP\)路径的记录.

我是不会记录路径的...(不知道自己为什么这么笨),参考了\(dalao\)的代码才发现...用\(tmp_i\)表示\(i\)从谁转移过来就行了...最后一次转移一定属于最优解.

性质里面说的第二条就是这题特殊的转移限制条件.

于是,就有了这个代码:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)#define per(i,a,b) for (int i = a ; i >= b ; -- i)#define int long longusing std::max ;using std::min ;const int N = 2e2 + 10 ;const int M = 1e6 + 100 ;char s[N][N] ;int e[N][N] , n , m ;int p[M] , f[M] , ans[M] , cnt , tmp[M] ;signed main () { scanf ("%lld" , & n ) ; rep ( i , 1 , n ) scanf ("%s" , s[i] + 1 ) ; scanf ("%lld" , & m ) ; rep ( i , 1 , m ) scanf ("%lld" , & p[i] ) ; rep ( i , 1 , n ) rep ( j , 1 , n ) e[i][j] = ( s[i][j] == '1' ? 1 : 0x7f7f7f7f ) ; rep ( i , 1 , n ) e[i][i] = 0 ; rep ( k , 1 , n ) rep ( i , 1 , n ) rep ( j , 1 , n ) e[i][j] = min ( e[i][j] , e[i][k] + e[k][j] ) ; MEM ( f , 0x7f ) ; f[1] = 1 ; rep ( i , 1 , m ) rep ( j , max ( i - n , 1ll ) , i - 1 ) if ( ( i - j ) == e[p[j]][p[i]] && f[i] > f[j] + 1 ) f[i] = f[j] + 1 , tmp[i] = j ; for (int i = m ; i ; i = tmp[i] ) ans[++cnt] = p[i] ; printf ("%lld\n" , f[m] ) ; per ( i , cnt , 2 ) printf ("%lld " , ans[i] ) ; printf ("%lld\n" , ans[1] ) ; system ("pause") ; return 0 ;}

转载于:https://www.cnblogs.com/Equinox-Flower/p/11400175.html

你可能感兴趣的文章