网站建设平台接单,wordpress添加表单,大同做网站,国外手机设计网站推荐根据题意要求的是将石子合并的最小权值#xff0c;我们可以根据DP思想使用二维数组f[i,j]来存放所有从第i堆石子到第j堆石子合并成一堆石子的合并方式。
然后由第二个图所示#xff0c;我们可以将i到j区间分成两个区间#xff0c;因为将i到j合并成一个区间的前一步一定是合… 根据题意要求的是将石子合并的最小权值我们可以根据DP思想使用二维数组f[i,j]来存放所有从第i堆石子到第j堆石子合并成一堆石子的合并方式。
然后由第二个图所示我们可以将i到j区间分成两个区间因为将i到j合并成一个区间的前一步一定是合并前两个区间。因此我们可以将状态计算的递归定义为区间的中间通过变化区间的中间来寻找合并i到j的最小值。
也就是f[i,j]min(f[i,k]f[k1,j]s[j]-s[i-1]
例题https://www.acwing.com/problem/content/284/
#includeiostream
using namespace std;const int N310;
int n;
int f[N][N];
int s[N];int main()
{cinn;int a;for(int i1;in;i) //前缀和{scanf(%d,a);s[i]s[i-1]a;}for(int len2;lenn;len){for(int i1;ilen-1n;i){int li ,rilen-1;f[l][r]1e8;for(int kl;kr;k){f[l][r]min(f[l][r],f[l][k]f[k1][r]s[r]-s[l-1]);}}}coutf[1][n];return 0;
}
k的取值范围:
这里划分出的区间是[l, k], [k1, r]
说明 [l, l] [r, r] 这两个区间都是不为空的至少包含了一堆石子。
前提划分出的两个区间都不为空的情况下讨论k的取值范围
所以对于[l, k] k可以取到 l 对于[k1, r] 因为k1 r, 所以 k r - 1, 即 k r
