浅说区间dp（下）

文章目录

• 环形区间dp
• 例题
• [NOI1995] 石子合并
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
    • 提示
    • 思路
    • [NOIP2006 提高组] 能量项链
    • • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
      • • 样例输入 #1
        • 样例输出 #1
        • 提示
        • 思路
        • [NOIP2001 提高组] 数的划分
        • • 题目描述
          • 输入格式
          • 输出格式
          • 样例 #1
          • • 样例输入 #1
            • 样例输出 #1
            • 提示
            • 思路
            • 放苹果
            • • 题目描述
              • 输入格式
              • 输出格式
              • 样例 #1
              • • 样例输入 #1
                • 样例输出 #1
                • 样例 #2
                • • 样例输入 #2
                  • 样例输出 #2
                  • 提示
                  • 思路
                  • 总结

                    环形区间dp

                    上一讲我们主要是讲解的链式的区间dp，但是我们经常会遇见一个环的dp问题，那么我们这时候应该怎么办呢，我们还是以一个生活例子来引入

                    又是wjq~~

                    

                    wjq又要开始合并衣服了，最近的wjq中了邪，喜欢圆圆的东西，所以这一次她把衣服放成了一个圆圈，总计有 N 件衣服，每件衣服有一个遮挡程度，现要将衣服有次序地合并成一堆，规定每次只能选相邻的 2 件合并成新的一堆，并将新的一堆的遮挡程度，记为该次合并的得分。

                    首先我们不难想到，每一件衣服都有可能是起点，所以我们现在就有以下几种情况：

                    假设现在圆圈里有“黑丝”，“白丝”，“泳装”，“jk”

                    那么我们就有：

                    “黑丝”，“白丝”，“泳装”，“jk”

                    “白丝”，“泳装”，“jk”，“黑丝”

                    “泳装”，“jk”，“黑丝”，“白丝”

                    “泳装”，“jk”，“黑丝”，“白丝”

                    总计四种情况

                    如果我们去找起点的话，太过繁琐了，那么我们来想想怎么优化。不难发现，当我们求解“黑丝”，“白丝”，“泳装”，“jk”时，“白丝”，“泳装”，“jk”，已经有了答案，那么我们在计算“白丝”，“泳装”，“jk”，“黑丝”的时候，就不用再次计算“白丝”，“泳装”，“jk”了，所以我们这里可以将整个数组copy一遍，放到后面，这样我们就可以避免重复计算了

                    这样无论哪个点为起点，再向后面枚举3个点都是一个完整的区间，即区间[i,i+n-1]为一个完整的区间。环变链后再做一次和前面一样的dp，注意下范围和边界，最后因为所有的长度为n的区间都有可能是答案，所以答案在min(dp[i,i+n-1])中。

                    要注意i要枚举到n的后面，因为后面的dp会用到这些值

                    这一招叫做化环为链，长度翻倍，是区间dp问题中常见的处理手段

                    ---

                    例题

                    [NOI1995] 石子合并

                    题目描述

                    在一个圆形操场的四周摆放 N N N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 2 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

                    试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分和最大得分。

                    输入格式

                    数据的第 1 1 1 行是正整数 N N N，表示有 N N N 堆石子。

                    第 2 2 2 行有 N N N 个整数，第 i i i 个整数 a i a_i ai​ 表示第 i i i 堆石子的个数。

                    输出格式

                    输出共 2 2 2 行，第 1 1 1 行为最小得分，第 2 2 2 行为最大得分。

                    样例 #1

                    样例输入 #1

                    4
                    4 5 9 4
                    

                    样例输出 #1

                    43
                    54
                    

                    提示

                    1 ≤ N ≤ 100 1\leq N\leq 100 1≤N≤100， 0 ≤ a i ≤ 20 0\leq a_i\leq 20 0≤ai​≤20。

                    思路

                    这道题其实和上面的引入大同小异，可以直接套用

                    #include 
                    using namespace std;
                    const int N = 300;
                    const int INF = 10e9;
                    int n, dp[N][N], dp2[N][N];
                    int sum[N], s[N];
                    int main(){
                    	cin >> n;
                    	for (int i = 1; i 
                     	   cin > s[i];
                     	   s[i + n] = s[i];
                    	}
                    	for(int i = 1; i 
                    		sum[i] = s[i] + sum[i - 1];
                      	}
                        for(int len = 1; len