最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界简讯:从合并石子学区间DP

来源：博客园


(资料图片仅供参考)

导读 ^ _ ^

区间DP是一种思考方式很不一样的DP问题。结合合并石头进行问题思考，你就能学会区间DP啦！

何为区间DP

其DP推导是在一个区间内进行的，通常DP数组代表某个区间的某些属性。当然，dp数组的推导非常麻烦。需要依据某种特定的顺序，进行dp推导。通常是 区间长度从小到大进行状态转移

合并石子

对于石头搬运的理解

最终的结果一定是两个合成一个，那么我们只要让合并的东西最小即可，如此递推下去。

推导状态转移

这里需要运用前缀和的思想，去舍掉无关石头的影响。

代码实现

#include#includeusing namespace std;const int N = 310;int n;int s[N];int f[N][N];int main( ) {scanf("%d",&n);for(int i = 1; i <= n; i++)     scanf("%d",&s[i]);//前缀和处理for(int i = 1; i <= n; i++) s[i] += s[i-1];//从区间长度小的开始枚举,len初始为2for(int len = 2; len <= n; len++)    for(int i = 1; i + len -1 <= n; i++) {     int l = i, r = i + len - 1;     f[l][r] = 1e8;     for (int k = l; k < r; k++) //这里k

#谢谢你的观看！

^ _ ^

关键词： 很不一样