C++(g++ 7.5.0) 解法, 执行用时: 617ms, 内存消耗: 33872K, 提交时间: 2022-09-16 10:14:56

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using PII = pair<int, int>;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> rcnt(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] == a[j]) {
                rcnt[i]++;
            }
        }
    }
    vector dp(n + 1, vector(n + 1, vector<int>(n + 1)));
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int k = 0; k <= rcnt[r]; k++) {
                dp[l][r][k] = max(dp[l][r][k], dp[l][r - 1][0] + (k + 1) * (k + 1));
                for (int i = l; i < r; i++) {
                    if (a[i] == a[r]) {
                        dp[l][r][k] = max(dp[l][r][k], dp[l][i][k + 1] + dp[i + 1][r - 1][0]);
                    }
                }
            }
        }
    }
    cout << dp[1][n][0] << '\n';
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cout << "Case " << i << ": ";
        solve();
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 266ms, 内存消耗: 32240K, 提交时间: 2019-09-25 14:55:23

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
int T,n,a[201],dis[201],f[201][201][201];
int main(){
    T=read();
    for(register int o=1;o<=T;++o)
    {
        n=read();
        memset(f,0,sizeof(f));
        memset(dis,0,sizeof(dis));
        for(register int i=1;i<=n;++i)a[i]=read();
        for(register int i=1;i<=n;++i)
            for(register int j=i+1;j<=n;++j)
                if(a[i]==a[j])dis[i]++;
        for(register int i=n;i>=1;--i)
            for(register int j=i;j<=n;++j)
            {
                for(register int k=0;k<=dis[j];++k)f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(k+1)*(k+1));
                for(register int k=i;k<j;++k)
                {
                    if(a[k]!=a[j])continue;
                    for(register int p=0;p<=dis[j];++p)f[i][j][p]=max(f[i][j][p],f[i][k][p+1]+f[k+1][j-1][0]);
                }
            }
        printf("Case %d: %d\n",o,f[1][n][0]);
    }
    return 0;
}

C++ 解法, 执行用时: 539ms, 内存消耗: 36744K, 提交时间: 2021-11-07 08:43:57

#include<bits/stdc++.h>
using namespace std;
int dp[210][210][210];
int a,col[210];
int t,hhh;
int dfs(int l,int r,int gs);
int main(){
	scanf("%d",&t);
	while(t--){
        hhh++;
		scanf("%d",&a);
		for(int i=1;i<=a;i++) scanf("%d",&col[i]);
		printf("Case %d: %d\n",hhh,dfs(1,a,1));
		memset(dp,0,sizeof(dp));
	}
	return 0;
}
int dfs(int l,int r,int gs){
	if(l==r) return gs*gs;
	if(l>r) return 0;
	if(dp[l][r][gs]) return dp[l][r][gs];
	dp[l][r][gs]=max(dfs(l,l,gs)+dfs(l+1,r,1),dfs(l,r-1,gs)+dfs(r,r,1));
	for(int i=l+1;i<=r;i++){
		if(col[i]==col[l]) dp[l][r][gs]=max(dp[l][r][gs],dfs(l+1,i-1,1)+dfs(i,r,gs+1));
	}
	return dp[l][r][gs];
}