3 条题解
-
1
剪贴板食用更加。
题意分析
求全题中的最优解,相当与把所有的石子堆按一个割点分割成两段。然后再分,再分,……,求最小的体力值。
所以这是一道很经典的区间dp。
前置知识
-
什么是区间dp
很简单(请原谅我使用如此恶劣的词汇),就是求一个区间的最优解。
-
递增公式
设有一个数串, 且 , , 则:
- 若已知右端点, 则的长度为
- 若已知左端点()和长度,则
- 若已知右端点()和长度,则
-
无穷大的C++版:0x3f3f3f3f,原因可看一下这篇博文,里面还把memset版的无穷大给写了出来。
思路
-
先枚举区间的长度
为什么呢?如果你去枚举端点,你无法保证区间长度递增,因此无法求得最优解。
-
再枚举起点,通过递增公式求出右端点,并保证右端点不越界。
-
枚举割点,把割点左边给合起来,右边的合起来,再把全部合起来,进行比较,即可得到一种解。求最小值即可。(可用前缀和来求整段的和)注意初始化dp数组为无穷大。
转移方程:$\red{dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+整段的和)}$
代码
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cctype> #include <iomanip> using namespace std; int dp[305][305]; int a[305], sum[305]; int n; int main() { int N; cin >> N; memset(dp,0x3f,sizeof(dp)); for (int i = 1;i <= N;i++) { dp[i][i] = 0; int x; cin >> x; sum[i] = sum[i - 1] + x; } for(int i = 2;i <= N;i++) { for(int l = 1,r = i;r <= N;l++,r++) { for(int k = l;k < r;k++) { dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + (sum[r] - sum[l-1])); } } } cout << dp[1][N]; }
-
信息
- ID
- 193
- 时间
- 5000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 196
- 已通过
- 64
- 上传者