洛谷P1880 石子合并 纪中2119. 环状石子归并

题目描述1

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

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

输入格式

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例

输入 #1复制

44 5 9 4

输出 #1复制

4354

---

(File IO): input:stone.in output:stone.out

时间限制: 1000 ms  空间限制: 262144 KB  具体限制  

题目描述2

  在一个环状跑道上摆放着N堆石子，现在要将所有的石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。问最少的总得分是多少？ 

输入

第一行为石子堆数N。

从第2行到第N + 1行，每行一个正整数。第i个数表示第i堆石子的石子数。

输出

在第一行输出一个整数，表示最少的总得分。

样例输入

4 4 5 9 4 

样例输出

43 

数据范围限制

在40%的数据中，1 ≤ N ≤ 100

在60%的数据中，1 ≤ N ≤ 200

在100%的数据中，1 ≤ N ≤ 2000

保证输入数据中每堆石子的石子数不超过10000 

Solution

此题为区间DP+四边形不等式

这是我第一次见到区间DP

洛谷上既要求最大值，也要求最小值，（多写几句话的事~）但是数据范围最大只有100

jzoj上就恶心了，虽然只要求最小值，但是数据范围最大为2000！

Algorithm1

标准的区间DP

由于这是环形的，所以要把整个跑道复制一遍

可以在输入的同时操作

（约定：s[i]表示第i（0~n-1）堆石子的数量）

for(int i=0;i
     
      >s[i],s[i+n]=s[i];
     

做DP前要先弄清楚“阶段”，“状态”，“决策”；

 

由于首先要合并两堆，再在两堆的基础上合并三堆，再在三堆的基础上合并四堆……以此类推。

并且，每次要选相邻的两堆合并（这就是为什么不能像“合并果子那样使用贪心”）

所以，每一个阶段就是合并去=的区间长度 len

这个len在循环的最外层，从2至n（最少合并2堆）

 

其次是状态

状态即为最初的第l堆石子和第r堆石子被合并，

同时l~r这段区间的长度为阶段——len。

所以我们要枚举的状态就是左端点

范围：左极限为0，右极限为右端点<n

 

最内层是决策

顾名思义：

就是决定当前应该选哪两堆来合并

对于目前长度为len的区间[l,r)

可以选出一个中间点k∈[l,r)

表示先合并了[l,k]，再合并[k+1,r)

所以决策就是中间点k

 

同时还要计算合并这两堆石子所需要的体力（即为两堆石子的石子数量之和）

可以使用前缀和计算

 

Code1

洛谷Code

1 #include
     
      //不想OI一场空，千万别用万能头 2 #include
      
       //快排sort() 3 #include
       
        //能不用cin就不用 4 #include
        
          5 #include
         
           6 #include
          
         
        
       
      
     

纪中Code1（70分）

1 #include
      
       //不想OI一场空，千万别用万能头 2 #include
       
        //快排sort() 3 #include
        
         //能不用cin就不用 4 #include
         
           5 #include
          
            6 #include
           
          
         
        
       
      

为什么折叠？

纪中此题的范围是2000，要用到四边形不等式优化成n²才能过……毒瘤呀

Attention1

所有数组都要开两倍大——这是环状变链状。

Algorithm2

四边形不等式

对于一个函数f(i,j)，有四个值a<=b<c<=d

使得f(a,b)+f(c,d)<f(a,c)+f(b,d)

那么这个函数满足四边形不等式

可以放到决策k时使用

至于证明嘛……打表证吧

 

 

 

 

 

 

 

 

 

 

Impression

2019-08-22 11:51:55

与此同时……

哪个人知道我们听不懂今天的讲课会都回来，故意放了比赛？？？