RT

link

目前写了个DP，希望大佬能找错

#include<iostream>
#include<string>
using namespace std;
string s[65];
int f[65][65][65],a[65][65];//f[i][j][k]为在前i个串中有j个被选中，目前是第k个串
int main(){
	int n,tor;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(j==i){
				continue;
			}
			a[i][j]=(s[i][s[i].length()-1]==s[j][0]);
		}
		a[i][0]=a[0][i]=1;
	}
	for(int i=1;i<=n;i++){
		f[i][i][i]=s[i].length();
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			tor=0;
			if(j<=i-1){
				for(int k=1;k<=i-1;k++){
					f[i][j][k]=f[i-1][j][k];
				}	
			}
			for(int k=0;k<=i-1;k++){
				if(a[k][i]||a[i][k]){
					tor=max(tor,f[i-1][j-1][k]+(int)s[i].length());
				}
			}
			f[i][j][i]=tor;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans=max(ans,f[n][i][j]);
		}
	}
	cout<<ans;
	return 0;
}