2020 昆明 C Cities

2020 昆明 C Cities

题目链接
思路：
考虑区间dp。
无法n^3的转移。
考虑如果一个区间如果左右两端左右端点相等(都是x),那么把这个区间的数都变成x的话所用步数最少。
然后因为同一种数最多出现15次，优化转移方法。

枚举一个区间时枚举左右两端相同的端点。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+150;
typedef long long ll;
int dp[N][N],a[N],vis[112345],last[N];
int main()
{ll t,n;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){last[i]=0;}for(int i=1;i<=n;i++){scanf("%d",&a[i]);last[vis[a[i]]]=i;vis[a[i]]=i;}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){dp[i][j]=112345678;}dp[i][i]=0;}for(int len=1;len<=n;len++){for(int i=1;i+len<=n;i++){int j=i+len;if(i==j)    {   dp[i][j]=dp[i][j-1];  continue;   }if(dp[i][j-1]<dp[i+1][j])dp[i][j]=dp[i][j-1]+1;elsedp[i][j]=dp[i+1][j]+1;int k=last[i];for(int k=last[i];k<=j;k=last[k]){if(k==0)break;if(dp[i][j]>(dp[i][k-1]+dp[k][j])){dp[i][j]=dp[i][k-1]+dp[k][j];break;}}}}for(int i=1;i<=n;i++){vis[a[i]]=0;}cout<<dp[1][n]<<endl;}return 0;
}