本文共 768 字，大约阅读时间需要 2 分钟。

定义$f[i][j]$为消除$[i,j]$的最小花费

如果$a[i]$和$a[j]$同色,那么可以消除中间再消两边

$f[i][j]=f[i+1][j-1]+(消除a_i,a_j的代价)$

也可以采用分段消除枚举分割点$k$

$f[i][j]=f[i][k]+f[k+1][j]$

一般的区间dp就这么完事了,但是这个不同

两端的球可以和中间某个球合并

$f[i][j]=f[i+1][k-1]+f[k+1][j-1]$

#include 
   
    using namespace std;const int maxn = 309;char s[maxn];int a[maxn],f[maxn][maxn],casenum;int main(){
   	int t; scanf("%d",&t);	while( t-- )	{
   		scanf("%s",s);		int n = strlen( s ),top=1;		a[top] = 1;		for(int i=1;i
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109738093 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！