CF1312E Array Shrinking's Solution
C C A
2020-03-11 12:54:18
# $CF1312E\ Array\ Shrinking's\ Solution$
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad By$ [$CCA$](https://www.luogu.com.cn/user/78645)
## $Problem$
$\qquad$给定一个数组，定义一次合并为对于两个相邻的数，如果他们相等，则可以将它们合并为一个数，其值为原数$+1$（参照$2048$）。问原数组合并完后的最小长度。
## $Solution$
$\qquad$这题十分套路。
$\qquad$我们考虑区间$DP$，令$dp[l][r]$表示$l$到$r$这段区间合并后的最小长度，同时，我们需要一个$w$数组来辅助计算，$w[l][r]$表示按照$dp[l][r]$合并完后，$l$到$r$这段区间的和是多少，转移很显然：
$$dp[l][r] = min\{dp[l][mid] + dp[mid + 1][r]\}$$
如果$dp[l][mid]=dp[mid + 1][r]=1$，并且$w[l][mid]=w[mid + 1][r]$，则：
$$dp[l][r] = 1 , w[l][r] = w[l][mid] + 1$$
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
int n , a[N] , dp[N][N] , w[N][N];
int main(){
memset(dp , 63 , sizeof(dp));
scanf("%d" , &n);
for(int i = 1; i <= n; i++)
scanf("%d" , &a[i]) , dp[i][i] = 1 , w[i][i] = a[i];
for(int k = 2; k <= n; k++)
for(int l = 1; l + k - 1 <= n; l++){
int r = l + k - 1;
for(int mid = l; mid < r; mid++){
dp[l][r] = min(dp[l][r] , dp[l][mid] + dp[mid + 1][r]);
if(dp[l][mid] == dp[mid + 1][r] && dp[l][mid] == 1 && w[l][mid] == w[mid + 1][r])
dp[l][r] = 1 , w[l][r] = w[l][mid] + 1;
}
}
printf("%d" , dp[1][n]);
return 0;
}
```
自认为码风还是比较清奇可看的，大家可以对着$Solution$仔细看一下。
最后，[$This\ is\ my\ blog$](https://www.luogu.com.cn/blog/A66-888/) , 有兴趣的可以逛一下，应该能有所收获。