BZOJ3229 石子合并

2021-11-27 19:36:37

Description

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

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

Input

　　第一行是一个数N。

　　以下N行每行一个数A，表示石子数目。

Output

　　共一个数，即N堆石子合并成一堆的最小得分。

Sample Input

4
1
1
1
1

Sample Output

HINT

对于 100% 的数据，1≤N≤40000

对于 100% 的数据，1≤A≤200

正解：GarsiaWachs算法

解题报告：

　　神奇的算法，居然可以把石子合并做到O（NlogN），不可思议，感到害怕。

　　上午讲题的时候提到了用四边形不等式得出的可以有单调性的N^2的优化DP，然而面对40000的数据还是有一点虚。

　　移步学习GarsiaWachs算法：http://www.cnblogs.com/lwq12138/p/5425465.html 或者 http://blog.csdn.net/Regina8023/article/details/45244733

　　不详细讲了。

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 #ifdef WIN32

 #define OT "%I64d"

 #else

 #define OT "%lld"

 #endif

 using namespace std;

 typedef long long LL;

 const int inf = ;

 const int MAXN = ;

 int a[MAXN];

 int n;

 LL ans;

 inline int getint()

 {

        int w=,q=;

        char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar();

        if (c=='-')  q=, c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar();

        return q ? -w : w;

 }

 inline void work(){

     n=getint();

     for(int i=;i<=n;i++) a[i]=getint();

     int m=n;

     a[]=a[n+]=inf;

     for(int i=;i<n;i++) {//最后一次不用做

     int k;

     for(int j=;j<=m;j++) {//从左往右，每次找到第一个满足a[k−1]≤a[k+1]的k，然后合并a[k−1],a[k]

         if(a[j-]<a[j+]) { k=j; break; }

     }

     a[k-]+=a[k];

     for(int j=k;j<m;j++) a[j]=a[j+];//左移

     ans+=a[k-]; k--;//指向当前处理结点

     while(k> && a[k-]<=a[k]) { //从当前位置开始向左找第一个a[j]>a[k−1]+a[k]的j，把合并后的值插到j的后面

         swap(a[k-],a[k]);

         k--;

     }

     a[m]=inf;

     m--;

     }

     printf(OT,ans);

 }

 int main()

 {

   work();

   return ;

 }

码农公寓