Untitled
unknown
plain_text
a month ago
1.0 kB
5
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(x) (x).begin(), (x).end() #define f(i, n) for (int i = 0; i < n; i++) #define trace(x) cerr << #x << ": " << x << '\n' string s, r; #define int long long const int N = 1e3 + 9; int n; int dp[N][N]; int fun(int i, int j) { if (i > j) return 0; if (dp[i][j] != -1) return dp[i][j]; int ans = fun(i + 1, j); ans = max(ans, fun(i, j - 1)); int ans2 = 1, in = -1; for (int k = j; k >= i; k--) { if (s[k] == s[i]) { in = k; break; } } if (in != -1) { if (i == in) ans2 = 1 + fun(i + 1, in - 1); else ans2 = fun(i + 1, in - 1) + 2; } return dp[i][j] = max(ans, ans2); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tt; cin >> tt; while (tt--) { memset(dp, -1, sizeof dp); cin >> s; n = s.size(); cout << fun(0, n - 1) << '\n'; } }
Leave a Comment