codeforces 1312E. Array Shrinking(区间dp)
codeforces 1312E. Array Shrinking
题意：
相同的两个 x x x可以合并成 x + 1 x+1 x+1，给一个序列，问最后数组中最少能剩下多少个数。
思路:
数据500，很明显的区间dp数据。
考虑之前区间 s u m [ 1 ] [ j ] sum[1] [j] sum[1][j]表示 i ， j i，j i，j合并以后能得到一个 k k k，如果 k = 0 k=0 k=0，表示不能合并到一起。
先预处理 s u m [ i ] [ j ] sum[i][j] sum[i][j]的元素个数为 j − i + 1 j-i+1 j−i+1， s u m [ i ] [ i ] = a [ i ] sum[i][i]=a[i] sum[i][i]=a[i]。
然后就是常规区间dp了，枚举区间长度，区间起点和区间终点。
只有当左区间和右区间的长度为1且左右区间各自合并出来的数字相等时才可以合并，即 s u m [ i ] [ k ] = = d p [ k + 1 ] [ j ] & & s u m [ i ] [ k ] > 0 sum[i][k]==dp[k+1][j]\&\&sum[i][k]>0 sum[i][k]==dp[k+1][j]&&sum[i][k]>0。
最后更新dp。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;
int a[maxn], dp[maxn], sum[maxn][maxn];
void solve(){
int n;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
sum[i][i] = a[i];
}
for (int len = 1; len <= n; len++){
for (int i = 1; i <= n - len; i++){
int j = len + i;
for (int k = i; k < j; k++){
if(sum[i][k] == sum[k+1][j] && sum[i][k] != 0){
sum[i][j] = sum[i][k] + 1;
}
}
}
}
dp[0] = 0;
for (int i = 1; i <= n; i++){
dp[i] = dp[i - 1] + 1;
for (int j = 1; j <= i; j++){
if(sum[j][i] > 0){
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
cout << dp[n] << endl;
}
int main(){
ios_base::sync_with_stdio(0);
solve();
return 0;
}
查看20道真题和解析