1 条题解

  • 1
    @ 2021-10-7 14:26:35
    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 210;
    int f[N][N][N];
    int len[N], a[N];
    int arr[N];
    int n;
    // 1 1  2 2 3 3 1 1 3 3 2 2 2 2 2
    // 2 2 2 2 2 5   len 
    // 1 2 3 1 1 2   a
    int init()
    {
        int j = 0;
        for(int i = 0 ; i <= n ; i ++)
        {
            if(i == 0)
            {
                len[j] = 1;
                a[j] = arr[i];
            }else if(arr[i] == arr[i - 1]){
                len[j] ++;
            }else{
                j ++;
                len[j] = 1;
                a[j] = arr[i];
            }
        }
        return j;  // len的长度
    }
    
    int dfs(int l, int r, int k)
    {
        if(l > r) 
            return f[l][r][k] = -100000; //不可能成立的情况
        if(l == r) 
            return f[l][r][k] = (len[r] + k) * (len[r] + k); //相当于循环写的初始化
        if(~f[l][r][k]) // 记忆话部分
            return f[l][r][k];
        int res = dfs(l, r - 1, 0) + (len[r] + k) * (len[r] + k);
        // 最后一个算一下
        for(int i = l ; i < r ; i ++) // 枚举分割方法
        {
            if(a[i] == a[r])
                res = max(res, dfs(i + 1, r - 1, 0) + dfs(l, i, len[r] + k));
        }
        return f[l][r][k] = res;
    }
    
    int main()
    {
        int T;
        cin >> T;
        for(int t = 1 ; t <= T ; t ++)
        {
            cin >> n;
            for(int i = 0 ; i < n ; i ++) 
                cin >> arr[i];
            n = init();  // 压缩
            memset(f, -1, sizeof f);
            cout << "Case " << t << ": " << dfs(0, n - 1, 0) << endl;
        }
        return 0;
    }
    
    • 1

    信息

    ID
    232
    时间
    1500ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    16
    已通过
    6
    上传者