[KOJ6024]合并果子·改（强化版）-白红宇

[KOJ6024]合并果子·改（强化版）

阅读量：5314 次

发布时间：2019-06-14

本文共 1968 字，大约阅读时间需要 6 分钟。

[COJ6024]合并果子·改（强化版）

试题描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多把这些果子堆排成一排，然后所有的果子合成一堆。

每一次合并，多多可以把相邻两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入

包括两行，第一行是一个整数n，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

输出

包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^63。

输入示例

41 2 5 2

输出示例

数据规模及约定

1<=n<=1000

题解

我们可以用的 dp 方法，然后进行优化。我们可以令 g[i][j] 表示 [i, j] 中最优合并方式的分界点，即使得 f[i][g[i][j]] + f[g[i][j]+1][j] 最小，不难发现 g[i][j-1] ≤ g[i][j] ≤ g[i+1][j]，于是 f[i][j] = min{ f[i][k] + f[k+1][j] + S(i,j) | g[i][j-1] ≤ k ≤ g[i+1][j] }，不难发现 (i - j + 1) 固定时，所有 g[i+1][j] - g[i][j-1] 之和是 n 的级别的，所以总时间复杂度变成了 O(n²).

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++;}int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 110#define oo (1ll << 63) - 1#define LL long longint n;LL S[maxn], f[maxn][maxn];int main() { n = read(); for(int i = 1; i <= n; i++) S[i] = S[i-1] + read(); for(int len = 2; len <= n; len++) for(int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; f[l][r] = oo; for(int k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k+1][r]); f[l][r] += S[r] - S[l-1]; } printf("%lld\n", f[1][n]); return 0;}

转载于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/5872672.html

你可能感兴趣的文章

面象对象设计原则之六：迪米特原则(LeastKnowledge Principle, LKP)