DP O(n^3)超时-> 换思路->栈

DP做法 会超时

#include<iostream>
#include<string>
using namespace std;
int ans;
bool dp[10005][10005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    for (int len = 2; len <= n; len += 2) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
            for (int k = i + 1; k < j; k += 2) {
                if (dp[i][k] && dp[k + 1][j]) {
                    dp[i][j] = true;
                    break;
                }
            }
            if (dp[i][j]) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

栈模拟

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    int ans = 0;

    for (int i = 0; i < n; i++) {
        stack<char> st;
        for (int j = i; j < n; j++) {
            if (!st.empty() && st.top() == s[j]) {
                st.pop();
            } else {
                st.push(s[j]);
            }

            if (st.empty() && (j - i + 1) % 2 == 0) {
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

洛谷对应题号
链接描述

制作不易，点个赞吧！🙆🙆🙆🙆😘😘