CodeForces1204C

CodeForces1204C

其实我觉得这是一道比较综合的题吧…
这个题可供挖掘的性质很多,比如最短路最长是$n$啊,答案序列中的两点之间的距离肯定是$p$数组上这两个点的距离啊等等.

其实是在$p$数组上进行了一次另类的最短子序列.图的条件其实就是限制了转移,然后再有一个有点意思的地方是$DP$路径的记录.
我是不会记录路径的…(不知道自己为什么这么笨),参考了$dalao$的代码才发现…用$tmp_i$表示$i$从谁转移过来就行了…最后一次转移一定属于最优解.
性质里面说的第二条就是这题特殊的转移限制条件.
于是,就有了这个代码:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#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 long

using 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 ;
}