京东 09.03笔试题解

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 20;
int n, a[MAXN], dp[MAXN];
int main(){
    scanf("%d", &n);
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[1] = 0;
    for(int i = 2; i <= 100000; i++){
        dp[i] = min(dp[i], dp[i - 1] + 1);
        for(int j = 1; j <= i / j; j++)
            if(i % j == 0)dp[i] = min(dp[i], dp[j] + dp[i / j] + 1);
    }
    LL ans = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        ans = ans + dp[a[i]];
    }
    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 10;
stack<int> s;
string str;
LL dp[MAXN];
int main(){
    cin >> str;
    int n = str.size();
    LL ans = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i - 1];
        if(str[i - 1] == '('){
            s.push(i);
        }
        else{
            if(!s.empty()){
                int pre = s.top(); s.pop();
                dp[i] = dp[i] + pre;
            }
        }
        ans = ans + dp[i];
    }
    cout << ans * 2 << endl;
    return 0;
}