51 nod 石子归并 + v2 + v3（区间dp，区间dp+平行四边形优化，GarsiaWachs算法）

题意：就是求石子归并。

题解：当范围在100左右是可以之间简单的区间dp，如果范围在1000左右就要考虑用平行四边形优化。

就是多加一个p[i][j]表示在i到j内的取最优解的位置k，注意能使用平行四边形优化的条件：

1.证明w满足四边形不等式，这里w是m的附属量，形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]}，此时大多要先证明w满足条件才能进一步证明m满足条件

2.证明m满足四边形不等式

3.证明s[i,j-1]≤s[i,j]≤s[i+1,j]

。如果在10000左右时就要用GarsiaWachs算法

 

推荐一个博客http://www.cnblogs.com/jiu0821/p/4493497.html

有详细解释。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int inf = 0X3f3f3f3f;

long long dp[200][200] , a[200] , sum[200];

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 1 ; i <= n ; i++) {

        scanf("%lld" , &a[i]);

    }

    memset(dp , inf , sizeof(dp));

    for(int i = 1 ; i <= n ; i++) {

        dp[i][i] = 0;

    }

    sum[0] = 0;

    for(int i = 1 ; i <= n ; i++) {

        sum[i] = sum[i - 1] + a[i];

    }

    for(int l = 1 ; l < n ; l++) {

        for(int i = 1 ; i <= n && i + l <= n ; i++) {

            int j = l + i;

            for(int k = i ; k < j ; k++) {

                dp[i][j] = min(dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1] , dp[i][j]);

            }

        }

    }

    printf("%lld\n" , dp[1][n]);

    return 0;

}

////////////

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int inf = 0X3f3f3f3f;

long long dp[2010][2010] , a[2010] , sum[2010] ;

int p[2010][2010];

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 1 ; i <= n ; i++) {

        scanf("%lld" , &a[i]);

    }

    memset(dp , inf , sizeof(dp));

    for(int i = 1 ; i <= 2 * n ; i++) {

        dp[i][i] = 0;

        p[i][i] = i;

    }

    sum[0] = 0;

    for(int i = n + 1 ; i <= 2 * n ; i++) {

        a[i] = a[i - n];

    }

    for(int i = 1 ; i <= 2 * n ; i++) {

        sum[i] = sum[i - 1] + a[i];

    }

    for(int l = 1 ; l < n ; l++) {

        for(int i = 1 ; i <= 2 * n && i + l <= 2 * n ; i++) {

            int j = l + i;

            for(int k = p[i][j - 1] ; k <= p[i + 1][j] ; k++) {

                if(dp[i][j] > dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]) {

                    dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];

                    p[i][j] = k;

                }

            }

        }

    }

    long long MIN = dp[1][n];

    for(int i = 2 ; i <= n ; i++) {

        MIN = min(MIN , dp[i][i + n - 1]);

    }

    printf("%lld\n" , MIN);

    return 0;

}

////////////////

#include <iostream>

#include <cstring>

using namespace std;

#define LL long long

const int MAXN = 50005;

int n, num;

LL ans;

int dp[MAXN];

void combine(int now) {

    int j;

    int temp = dp[now - 1] + dp[now];

    ans += (LL)temp;

    for(int i = now; i < num - 1; i++) dp[i] = dp[i + 1];

    num--;

    for(j = now - 1; j > 0 && dp[j - 1] < temp; j--) dp[j] = dp[j - 1];

    dp[j] = temp;

    while(j >= 2 && dp[j - 2] <= dp[j]) {

        int d = num - j;

        combine(j - 1);

        j = num - d;

    }

}

int main()

{

    scanf("%d", &n);

    for(int i = 0; i < n; i++) scanf("%d", &dp[i]);

    num = 1, ans = 0;

    for(int i = 1; i < n; i++)

    {

        dp[num++] = dp[i];

        while(num>=3 && dp[num-3]<=dp[num-1]) combine(num - 2);

    }

    while(num > 1) combine(num - 1);

    printf("%lld\n", ans);

    return 0;

}