生活随笔
收集整理的這篇文章主要介紹了
CodeForces Gym 100989B LCS (B)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
給一個算LCS時得到的DP矩陣，然后根據這個矩陣讓你算出兩個符合條件的字符串
因為字符串長度<=25，然后可以先假設A字符串就是abcdef....，然后根據A算B就行，看B中哪個跟A一樣，但是A中可能有兩個或以上的字符跟B的某個是一樣的，然后這時就要把這兩個變成同一個，但是這個涉及到很多，因為可能還跟B中別的字符一樣，所以就 用并查集維護他們，把他們并到一個集合里，最后輸出時按集合的根輸出就行。
或者不用并查集，每次遇到這 個問題時，就把AB字符串都掃一遍，遇到要改的改掉就行，反正長度 25，隨便搞
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
int R, C;
char A[30], B[30];
int DP[30][30];
int set[30];
int stk[30];
int findset(int x)
{if (x == set[x])return x;elsereturn set[x] = findset(set[x]);
}
void unionset(int x, int y)
{int fx = findset(x);int fy = findset(y);if (fx == fy)return;elseset[fy] = fx;findset(y);
}
int main()
{//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);scanf("%d%d", &R, &C);for (int i = 0; i <= R; ++i){for (int j = 0; j <= C; ++j){scanf("%d", &DP[i][j]);}}for (int i = 1; i <= R; ++i){A[i] = 'a' + i - 1;set[i] = i;}int cnt = 0;for (int j = 1; j <= C; ++j){cnt = 0;for (int i = 1; i <= R; ++i){if (DP[i][j] > DP[i - 1][j] && DP[i][j] > DP[i][j - 1]){stk[cnt++] = i;}}for (int i = 1; i < cnt; ++i)unionset(stk[0], stk[i]);}for (int i = 1; i <= R; ++i){findset(i);}for (int i = 1; i <= R; ++i)A[i] = A[findset(i)];for (int i = 1; i <= C; ++i){if (B[i] == 0)B[i] = 'z';}for (int j = 1; j <= C; ++j){cnt = 0;for (int i = 1; i <= R; ++i){if (DP[i][j] > DP[i - 1][j] && DP[i][j] > DP[i][j - 1]){B[j] = A[set[i]];}}}printf("%s\n", A + 1);printf("%s\n", B + 1);//system("pause");//while (1);return 0;
}
總結
以上是生活随笔為你收集整理的CodeForces Gym 100989B LCS (B)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
