제출 #561640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561640		fatemetmhr	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	514 ms	146476 KiB

copypaste3

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second

const int maxn5 = 2e2 + 5;
const int maxnt = 8e5 + 10;
const ll  inf   = 1e15;

ll dp[maxn5][maxn5][maxn5], cost[maxn5][maxn5];
bool is_equa[maxn5][maxn5][maxn5];


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, a, b, c; string s;
    cin >> n >> s >> a >> b >> c;

    for(int len = 2; len <= n; len++) for(int l = 0; l + len - 1 < n; l++) for(int k = 1; k * 2 <= len; k++){
        int r = l + len - 1;
        if(k == 1)
            is_equa[l][r][k] = (s[l] == s[r]);
        else
            is_equa[l][r][k] = (s[l + k - 1] == s[r]) && is_equa[l][r - 1][k - 1];
    }

    //cout << is_equa[2][7][2] << ' ' << is_equa[2][7][3] << endl;

    for(int len = 1; len <= n; len++) for(int l = 0; l + len - 1 < n; l++){
        int r = l + len - 1;
        for(int k = 1; k <= len; k++){
            if(k == len){
                dp[l][r][k] = c;
                continue;
            }

            dp[l][r][k] = dp[l + 1][r][k] + a;
            if(k * 2 <= len && is_equa[l][r][k])
                dp[l][r][k] = min(dp[l][r][k], dp[l + k][r][k] + c);
        }
    }

    for(int i = 0; i < n; i++)
        cost[i][i] = a;

    for(int len = 2; len <= n; len++) for(int l = 0; l + len - 1 < n; l++){
        int r = l + len - 1;
        cost[l][r] = min(a + cost[l + 1][r], a + cost[l][r - 1]);
        //cout << "begin " << l << ' ' << r << ' '<< cost[l][r] << ' ' << a << ' ' << len << endl;
        for(int k = 1; k * 2 <= len; k++) if(is_equa[l][r][k]){
            cost[l][r] = min(cost[l][r], cost[l][l + k - 1] + b + c + dp[l + k][r][k]);
            //cout << l << ' '<< r << ' ' << k << ' ' << cost[l][r] << endl;
        }
    }

    cout << cost[0][n - 1] << endl;

}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38