石子合并 HYSBZ 3229 区间dp，最优二叉树问题，加西亚瓦克斯算法（GarsiaWachs）

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

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

 

Input

　　第一行是一个数 N 。

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

 

Output

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

 

Sample Input4 1 1 1 1 Sample Output8 Hint

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

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

一开始一直用区间动规，无奈只能过n小的，

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include<cstring>
#include <algorithm>
#include <queue>
#include<map>
using namespace std;
typedef long long ll;
const ll inf = 1<<30;
const int mod = 1000000007;
const int mx = 300; //check the limits, dummy
typedef pair<int, int> pa;
const double PI = acos(-1);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
#define swa(a,b) a^=b^=a^=b
#define re(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define rb(i,a,b) for(int i=(b),_=(a);i>=_;i--)
#define clr(a) memset(a, -1, sizeof(a))
#define lowbit(x) ((x)&(x-1))
#define mkp make_pai
//void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); }
int n, m, k,ans;
int sum[mx];
int minval() {
    int dp[mx][mx];
    re(i, 1, n + 1) {
        dp[i][i] = 0;
    }
    re(len,1,n)//len 是i,j间距离
        re(i, 1, n - len + 1) {//start from the ith heap
        int j = i + len;//end at the jth heap
        dp[i][j] = inf;
        re(k,i,j)//dp[i][j]=min(dp[i][k],dp[k+1][j])+sum[i][j-i+1],i<=k<=j状态转移方程            
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);        
    }
    return dp[1][n];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while (cin >> n) {
        clr(sum);
        re(i, 1, n + 1) {
            int x;
            cin >> x;
            sum[i] = sum[i - 1] + x;//sum[i,j]=sum[j]-sum[i-1]
        }
        cout << minval() << endl;
    }
    return 0;
}

网上找了一个奇淫的算法加西亚-瓦克斯算法（GarsiaWachs）

 

 

 这个算法的时间效率和快速排序差不多，最坏情况是n^2

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, low = 1, list[40005];
    long long ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%d", &list[i]);
    while (low < n - 1)
    {
        int i;
        for (i = low; i < n - 1; i++)if (list[i] <= list[i + 2])
        {
            list[i + 1] += list[i], ans += list[i + 1];
            for (int j = i; j > low; j--)list[j] = list[j - 1];
            low++;
            int j = i + 1;
            while (list[j] > list[j - 1] && j > low)
            {
                list[j] ^= list[j - 1] ^= list[j] ^= list[j - 1];
                j--;
            }
            break;
        }
        if (i == n - 1)
        {
            list[n - 1] += list[n];
            ans += list[--n];
        }
    }
    if (low == n - 1)ans += list[n - 1] + list[n];
    cout << ans;
    return 0;
}