結果

問題 No.1512 作文
ユーザー qwewe
提出日時 2025-05-14 13:03:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,064 bytes
コンパイル時間 724 ms
コンパイル使用メモリ 81,268 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:04:50
合計ジャッジ時間 2,423 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Needed for max

using namespace std;

// Use long long for lengths as the total length can potentially be large.
// The problem states the sum of |S_i| is at most 200000, which fits in a 32-bit signed integer.
// However, using long long is safer and handles larger potential sums if constraints were different.
typedef long long ll;

// Function to check if a string is "good".
// A string is good if its characters are in non-decreasing alphabetical order.
bool is_good(const string& s) {
    // An empty string is considered good according to the problem statement examples.
    // However, the constraint |S_i| >= 1 means we won't receive empty strings as input.
    // If the string has 0 or 1 character, it's automatically good.
    if (s.length() <= 1) {
        return true;
    }
    // Check adjacent characters
    for (size_t i = 0; i + 1 < s.length(); ++i) {
        // If we find a pair where the current character is greater than the next one,
        // the string is not sorted non-decreasingly, hence not good.
        if (s[i] > s[i+1]) {
            return false; 
        }
    }
    // If we iterated through all adjacent pairs and found no violations, the string is good.
    return true; 
}

int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Number of strings
    cin >> N;

    // L[c1][c2] will store the total length of all good input strings S_i
    // such that S_i starts with character 'a'+c1 and ends with character 'a'+c2.
    // We use a 2D vector of size 26x26, initialized to zeros.
    vector<vector<ll>> L(26, vector<ll>(26, 0));

    // Read N strings, check if each is good, and if so, aggregate its length into the L table.
    for (int i = 0; i < N; ++i) {
        string S;
        cin >> S;
        // The problem guarantees |S_i| >= 1, so strings are non-empty.
        if (is_good(S)) {
            // Get the 0-based indices for the first and last characters.
            int first_char_idx = S.front() - 'a';
            int last_char_idx = S.back() - 'a';
            // Add the length of the good string to the corresponding cell in L.
            L[first_char_idx][last_char_idx] += S.length();
        }
    }
    
    // Dynamic Programming approach:
    // dp[i] will store the maximum length of a good concatenated string
    // that ends with the character 'a'+i.
    vector<ll> dp(26, 0);
    
    // This variable tracks the maximum value found in dp[k] for all k < i processed so far.
    // It represents the maximum length of a good concatenated string ending *before* the current character 'a'+i.
    ll max_dp_prefix = 0; 

    // Iterate through all possible ending characters 'a' through 'z' (indices 0 to 25).
    for (int i = 0; i < 26; ++i) {
        // Calculate term1: Represents the maximum length achieved by appending a block of strings
        // that start at character 'a'+j (where j < i) and end at character 'a'+i.
        // This block must follow a path ending at 'a'+j. The max length for such path is dp[j].
        // We take the maximum over all possible previous characters 'a'+j.
        ll term1 = 0;
        for (int j = 0; j < i; ++j) {
             // We can only transition from j to i if there exist good strings starting at 'a'+j and ending at 'a'+i.
             // This is indicated by L[j][i] > 0.
             if (L[j][i] > 0) { 
                  // The length would be the max length ending at j (dp[j]) plus the total length of strings from j to i (L[j][i]).
                  term1 = max(term1, dp[j] + L[j][i]);
             }
        }
        
        // Calculate term2: Represents the maximum length achieved by potentially appending a block of strings
        // that both start and end at character 'a'+i (total length L[i][i]).
        // Such a block can follow any path that ends at a character 'a'+k where k < i.
        // The maximum length among such preceding paths is captured by max_dp_prefix.
        ll term2 = max_dp_prefix + L[i][i];

        // The maximum length ending at character 'a'+i (dp[i]) is the maximum of the two possibilities calculated above.
        // Note that if L[i][i] is 0, term2 effectively represents just continuing a path from before 'i' without adding strings starting and ending at 'i'.
        // If L[j][i] is 0 for all j < i, term1 will be 0.
        // dp[i] calculation correctly covers cases where paths start fresh with strings corresponding to L[j][i] or L[i][i].
        dp[i] = max(term1, term2);

        // Update max_dp_prefix to include the newly computed dp[i].
        // This ensures max_dp_prefix stores max(dp[k] for k <= i) for the next iteration.
        max_dp_prefix = max(max_dp_prefix, dp[i]);
    }

    // After iterating through all characters, max_dp_prefix holds the maximum value across all dp[i],
    // which corresponds to the maximum possible length of a good concatenated string.
    cout << max_dp_prefix << endl;

    return 0;
}
0