結果
問題 | No.1512 作文 |
ユーザー |
![]() |
提出日時 | 2021-05-21 21:46:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,183 bytes |
コンパイル時間 | 4,788 ms |
コンパイル使用メモリ | 207,888 KB |
最終ジャッジ日時 | 2025-01-21 14:47:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include "bits/stdc++.h"#define int long longusing namespace std;using ll = long long;using P = pair<ll, ll>;const ll INF = (1LL << 61);ll mod = 1000000007;int dp[27];signed main() {ios::sync_with_stdio(false);cin.tie(0);int N; cin >> N;vector<string>S(N);for (int i = 0; i < N; i++)cin >> S[i];sort(S.begin(), S.end());vector<bool>c(N);for (int i = 0; i < N; i++) {bool ok = true;for (int j = 0; j < (int)S[i].size() - 1; j++) {if (S[i][j] > S[i][j + 1])ok = false;}c[i] = ok;}vector<vector<int>>cost(26, vector<int>(26, -INF));for (int i = 0; i < N; i++) {if (!c[i])continue;char f = S[i][0], e = S[i].back();if (f == e) {cost[f - 'a'][e - 'a'] = max(cost[f - 'a'][e - 'a'], 0LL);cost[f - 'a'][e - 'a'] += (int)S[i].size();}else cost[f - 'a'][e - 'a'] = max(cost[f - 'a'][e - 'a'], (int)S[i].size());}for (int i = 0; i < 26; i++) {for (int j = 0; j < 26; j++) {int ma = 0;for (int k = 0; k <= i; k++) {ma = max(ma, dp[k] + cost[i][j]);}dp[j] = max(dp[j], ma);}}int ans = 0;for (int i = 0; i < 26; i++) {ans = max(ans, dp[i]);}cout << ans << endl;return 0;}