CodeForces1204C

小咪咪 2023-06-02 11:57 12阅读 0赞

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

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

[CodeForces1204C]: http://codeforces.com/contest/1204/problem/C