总结

今天和昨天一样在讲DP的优化。不过今天与昨天的区别就在于今天的题目更需要找到题目中的细节。比如一会儿要写的吞并序列，里面就有一个非常坑的一个细节。

在DP的时候。我们要关注题目里面一些数据非常小的点。比如状压DP的时候我们会发现我们要状压的部分非常小。但是我们把它写进维度里面又不好写。

DP优化也是一样，我们需要关注题目里面非常特殊的数据。以及部分分时的特殊条件。这些都有可能成为破题的关键。

举个例子，E* 吞并序列（题解）

题目简述

给你一个长度为 \(n\) 的序列 \(a\)。你现在可以将一段连续的且在 \(a\) 中这一段 \(a_i\) 的值都一样。你可以将这一段修改为 \(k\)。求将 \(a\) 修改成全部一样的最小操作次数。

解法

现在想想最暴力的方法应该怎么做。

不难发现，这道题我们可以用区间DP做。（虽然我去做线性DP了。。。（错的））

那么区间DP最大的传统就是 \(dp_{i,j}\) 。具体含义就是 \([i,j]\) 这个区间里面我可以省略多少次操作（因为我们会发现每一两个相同的它就可以省略）。接下来考虑转移。

\[dp_{i,j}=\max(dp_{i,k-1}+dp_{i,k}+1(a_k=a_i),dp_{i+1,j}) \]

初始化即为 \(dp_{i,i}=0\)。最终的答案即为 \(n-1-dp_{1,n}\)。

这个就是暴力的做法了。

接下来考虑怎么优化。

会发现满足上面的式子的 \(k\) 很少。因为每个数字最多只会出现15次。

所以我就可以记录当前这个数字，它下一次出现的位置是在哪儿。如果说没有即为零。

那么现在这道题就做完了，时间复杂度为 \(O(15n^2)\)。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=5005;
int a[maxn],dp[maxn][maxn],pos[maxn],nxt[maxn];
signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;int n;while(t--){for(int i=1;i<=n;i++) dp[i][i]=0;cin>>n;for(int i=1;i<=n;i++) dp[i][i]=0;for(int i=1;i<=n;i++) cin>>a[i],pos[i]=0;for(int i=n;i>=1;i--){nxt[i]=pos[a[i]];pos[a[i]]=i;}for(int len=1;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;dp[i][j]=dp[i+1][j];int x=nxt[i];while(x!=0&&x<=j){dp[i][j]=max(dp[i][j],dp[i+1][x-1]+dp[x][j]+1);x=nxt[x];}}}cout<<n-1-dp[1][n]<<endl;}return 0;
}