一本通1274 合并石子

区间dp 的入门题

dpi,jdp_{i,j}[i,j][i,j] 区间中的最小得分

区间dp一般是对于每个区间 [i,j][i,j] 枚举一个 kk 将区间 [i,j][i,j] 切为两端并计算总区间代价

得出转移方程: dpi,j=min{dpi,k+dpk+1,j+l=ijarrl}dp_{i,j} = min\{dp_{i,k} + dp_{k+1,j} + \sum\limits_{l=i}^{j}arr_l\}

代码中需要使用前缀和预处理掉方程中的那个 ll 省去一个 nn 的时间复杂度

最终复杂度 O(n3)O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstring>
using namespace std;
int n,arr[110],psum[110],dp[110][110];
int main(){
memset(dp,0x3f,sizeof(dp));
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i],psum[i] = psum[i-1] + arr[i],dp[i][i] = 0;
for(int i=n-1;i>=1;i--)
for(int j=i+1;j<=n;j++)
for(int k=i;k<j;k++)
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+psum[j]-psum[i-1]);
cout << dp[1][n] << endl;
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!