【整理】石子合并问题（四边形不等式DP优化）

有很多种算法：

1，任意两堆可以合并：贪心+单调队列。

2，相邻两堆可合并：区间DP (O(n^3)) ）。

3，相邻，四边形不等式优化DP （O(n^2) ）。

4，相邻，GarsiaWachs算法（O(nlgn)）。

这里实现了第2，3种解法：（个人的区间DP习惯从后面向前面扫）

看起来第四种还是比较重要的，有空再搞。

2：暴力DP

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>

using namespace std;
const int inf=1000000000;
int a[110],dp[110][110],sum[110];
int main()
{
    int n,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++) dp[i][j]=inf;
    for(i=1;i<=n;i++) dp[i][i]=0;
    
    for(i=n-1;i>=1;i--)
       for(j=i+1;j<=n;j++)
         for(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("%d
",dp[1][n]);
    return 0;
}

3：优化DP

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#define LL long long
using namespace std;
LL min(LL a,LL b){
    if(a<b) return a;return b;
}
const LL inf=1000000000000000000;
LL a[2200],dp[2200][2200],sum[2200];
LL s[2200][2200],ans=inf; 
int main()
{
    LL n,i,j,k;
    scanf("%lld",&n);
    for(i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        a[i+n]=a[i];
    }
    for(i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
    for(i=1;i<=2*n;i++)
        for(j=1;j<=2*n;j++) 
            dp[i][j]=(i==j?0:inf);

    for(i=2*n-1;i>=1;i--)
       for(j=i+1;j<=2*n;j++){
         LL L=s[i][j-1]?s[i][j-1]:i;
         LL R=s[i+1][j]?s[i+1][j]:n+n;
         for(k=L;k<=R;k++){
                LL  tmp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                if(dp[i][j]>tmp){
                    dp[i][j]=tmp;
                    s[i][j]=k;
                }
         }
    }    
    for(i=1;i<=n;i++)
     ans=min(ans,dp[i][i+n-1]);
    printf("%lld
",ans);
    return 0;
}

【整理】石子合并问题（四边形不等式DP优化）

相关推荐