HihoCoder - 1636 Pangu and Stones——区间dp

HihoCoder - 1636 Pangu and Stones——区间dp

题意：在石子合并的基础上做了限制，规定每次至少合并连续l堆石子，至多合并r堆石子

思路：定义dp【i】【j】【k】为区间【i，j】包含k堆石子时的最小值， 最终结果就是dp【1】【n】【1】，即整个区间最终合并为1堆的最小值，明显dp【i】【j】【1】是求解的重点。

求解dp【i】【j】【1】的状态转移方程为：dp【i】【j】【1】 = min（dp【i】【j】【1】， dp【i】【j】【k】 + sum【j】 - sum【i-1】）（2 《= k 《= r（r是题目给定的））

其中sum【】预处理前缀和，用于计算任意一段连续区间的和，很明显如果想要把区间【i，j】中的所有堆合并为1个堆，无论如何都要花费这个区间的总和，dp【i】【j】【k】（2 《= k 《= r）则是枚举不同的划分，最终找到一个最小值

求解dp【i】【j】【k】（2 《= k 《= r）的状态转移方程为：dp【i】【j】【k】 = min（dp【i】【j】【k】， dp【i】【p】【1】+dp【p+1】【j】【k-1】）（i《=p《j）

p是把区间【i，j】一切两半，则dp【i】【j】【k】就是左半边【i，p】划分成1堆、右半边【p+1，j】划分成k-1堆转移而来，至于为什么不加sum【j】 - sum【i - 1】，是因为我们的合并过程是在dp【i】【j】【1】中完成的，在dp【i】【j】【k】（2 《= k 《= r）中我们只负责划分，不进行合并，这也是这道题的巧妙之处。

#include #include #include #include using namespace std;const int maxn = 105;const int INF = 0x3f3f3f3f;int n, l, r, a[maxn], sum[maxn], dp[maxn][maxn][maxn];int main() { while (~scanf("%d %d %d", &n, &l, &r)) { sum[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } memset(dp, INF, sizeof(dp)); for (int i = 1; i <= n; i++) dp[i][i][1] = 0; for (int len = 1; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; for (int k = min(r, len); k >= 2; k--) { for (int p = i; p < j && j - p >= k - 1; p++) { dp[i][j][k] = min(dp[i][j][k], dp[i][p][1] + dp[p+1][j][k-1]); } if (k >= l) dp[i][j][1] = min(dp[i][j][1], dp[i][j][k] + sum[j] - sum[i-1]); } } } printf("%d\n", dp[1][n][1] == INF ? 0 : dp[1][n][1]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。