题目链接：https://codeforces.ml/contest/1312/problem/E
题目大意：给你一个数组，两个相邻的相同元素X可以合并成一个元素X+1。可以无限次合并。问最后数组剩余的最少元素。
我们用dp[i]表示前i个元素可以合并成的最小元素数量。考虑转移:如果a[1]−a[i]的某个后缀a[x]−a[i]可以合并成一个元素。那么就可以dp[i]=min(dp[i],dp[x−1]+1)。所以我们要预处理所有位置的X。对于一个区间是否能合并成一个元素可以用栈模拟就可以了。这个地方可以类似区间dp:枚举区间长度和区间起点来处理每个区间O(N3)当然我们分析区间[l,r]和区间[l,r+1]只添加了一个元素。如果我们枚举区间起点和区间终点就可以栈复用O(N2)。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int a[505], f[505], dp[505];
vector<int> v[505];
int main() {
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
f[i]=i; dp[i]=i;
}
for(int l=1; l<=n; l++){
stack<int> s;
for(int r=l; r<=n; r++){
int pos=a[r];
while(!s.empty()&&s.top()==pos){
s.pop(); pos++;
}
s.push(pos);
if(s.size()==1){
v[r].push_back(l);
}
}
}
for(int i=1; i<=n; i++){
for(int j=0; j<v[i].size(); j++){
dp[i]=min(dp[i], dp[v[i][j]-1]+1);
}
}
cout<<dp[n]<<endl;
return 0;
}
京公网安备 11010502036488号