CF1572C题解

· · 题解

这题不该标紫啊

首先，来一个简单算法：可以统计颜色块的个数，一个一个暴力修改为最后想要的颜色，就可以得到一个可行解。

然而，我们现在要讨论最优解比可行解少在了哪。举个例子：

$1,1,1 2 1,1,1

答案也就会是 3 。但是，如果我们先将中间的 2 改为 1 的话，我们的任务就直接完成了

由此，我们可以得出一个小结论：只要我们能通过修改中间的颜色块，使得左右两个相同颜色的颜色块相连，就会使答案减少。

同时，有一个比较显然的结论：将每个颜色块在修改时把它的颜色改为它后面紧接着的颜色块的颜色，答案不会更劣（自行证明）。

所以现在我们可以设计状态。f[i][j]表示把从i到j所有的颜色块改为一样颜色所用的最少步数。由上面两个结论可以导出：f[i][j]=min(f[i][j-1]+1,f[i][sm[a[i]]]+f[sm[a[i]]+1][j]);其中sm[a[i]]表示在i之前和a[i]相同颜色的位置。

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
int buc[3005],a[3005],lst[3005];
int f[3005][3005];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        buc[a[i]]=0;
    }
    for(int i=1;i<=n;i++)
    {
        lst[i]=buc[a[i]];
        buc[a[i]]=i;
    }
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i+l-1<=n;i++)
        {
            int j=i+l-1;
            f[i][j]=f[i][j-1]+1;
            for(int k=lst[j];k>=i;k=lst[k])
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
    }
    cout<<f[1][n]<<endl;
}
signed main(){
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
#if __MY_TEST__
    fclose(stdin);
    fclose(stdout);
#endif
}