【題解】Codeforces 919D. Substring

【題目敘述】https://codeforces.com/contest/919/problem/D
【解題想法】拓撲排序 (Topological sorting) + DP

  • 題目說明輸入字串只含「小寫字母」,以陣列空間0~25紀錄即可。
  • 可能有環,或者“graph can be not connected“。以vector (ans)紀錄走過的節點,判斷是否有解。
  • 進行有向圖的拓撲排序。
  • dp[i][j]:紀錄行經node-i時,每個字母最多被使用幾次。
  • 最後 ans 的長度若不等於 n (節點數目),無解。
  • 否則,max(dp[ ][ ]) 即為答案。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector <int> v[300005];
vector <int> ans;
int dp[300005][26];
int n, m, in[300005], now, a, b, mx;
string s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
        in[b]++;
    }
    queue <int> q;
    for (int i = 0; i < n; i++){
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()){
        now = q.front();
        q.pop();
        ans.push_back(now);
        dp[now][s[now]-'a']++;
        for (int i:v[now]){
            in[i]--;
            for (int j = 0; j < 26; j++){
                dp[i][j] = max(dp[now][j], dp[i][j]);
            }
            if (in[i] == 0)q.push(i);
        }
    }
    if (ans.size() != n) cout << "-1";
    else{
        mx = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 26; j++){
                mx = max(mx, dp[i][j]);
            }
        }
        cout << mx << "\n";
    }
}
分享本文 Share with friends