活動(dòng)地址： ?？痛赫兴㈩}訓(xùn)練營(yíng) - 編程打卡活動(dòng)

簡(jiǎn)單題 a的翻轉(zhuǎn)

可以用 stoi() 函數(shù)計(jì)算字符串對(duì)應(yīng)的整數(shù)值。
分別計(jì)算原字符串對(duì)應(yīng)的整數(shù)，和反轉(zhuǎn)后的字符串對(duì)應(yīng)的整數(shù)，然后相加輸出答案。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    string b = s;
    reverse(b.begin(), b.end());
    cout << stoi(s) + stoi(b);
    return 0;
}

中等題 斐波那契數(shù)列

和昨天跳臺(tái)階完全相同的做法。
直接偷懶貼代碼來了

#include <iostream>
using namespace std;
int fib(int number) {
    if (number <= 2)return 1;
    int a1 = 1, a2 = 1, a3;
    for (int i = 1; i <= number - 2; i++) {
        a3 = a1 + a2;
        a1 = a2;
        a2 = a3;
    }
    return a3;
}
int main() {
    int n;
    cin >> n;
    cout << jumpFloor(n);
    return 0;
}

困難題 括號(hào)區(qū)間匹配

區(qū)間dp。
設(shè) 為 這個(gè)區(qū)間形成括號(hào)匹配的字符串最少需要添加的字符數(shù)。
首先枚舉長(zhǎng)度為 的區(qū)間， 固定為 。
然后枚舉長(zhǎng)度為 的區(qū)間，如果這個(gè)區(qū)間是匹配的括號(hào)， 值為 ，否則為 。
然后長(zhǎng)度從 開始枚舉到 ，記枚舉到的左右端點(diǎn)分別為 ，當(dāng) 可以和 匹配時(shí)，，否則 。
最后是區(qū)間dp常用套路：枚舉斷點(diǎn) 從 到 ，。

#include <bits/stdc++.h>
using namespace std;
int dp[102][102];
int main() {
    string s;
    cin >> s;
    int n = s.length();
    s = ' ' + s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = n;
    for (int i = 1; i <= n; i++)dp[i][i] = 1;
    for (int i = 1; i + 1 <= n; i++)
        if ((s[i] == '(' && s[i + 1] == ')') || (s[i] == '[' && s[i + 1] == ']'))
            dp[i][i + 1] = 0;
        else
            dp[i][i + 1] = 2;    
    for (int len = 3; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']'))
                dp[l][r] = dp[l + 1][r - 1];
            else
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;
            for(int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);    
        }
    }
    cout << dp[1][n];
    return 0;
}