区间DP经典石子合并

题意：环形的一群石子，每次可以选择相邻的两堆合并，分数为新得到的一堆石子，求将这片石子合并成一堆的最大和最小分数

输入：第一行一个正整数n，其后n个数代表每堆石子的个数

分析：第一次写的时候我想当然的写的状态转移方程是dpx[l][r]=max(dpx[l+1][r]+a[l][r],dpx[l][r-1]+a[l][r]);(dpx是指这个dp数组用来求最大分数)，想的是左右逼近，但是我这个状态转移方程有个非常致命的缺点，那就是合并的两堆石头，一定有一堆是没经过合并的，这很明显无法代表全部情况，万一正解就是左边一半合并成一起，右边一半合并成一起，然后左右合并，我的算法就肯定得不到答案。

搜了搜正解，正解状态转移方程是dp1[l][r]=max(dp1[l][r],dp1[l][k]+dp1[k+1][r]+d(l,r));通过枚举一个k来实现将左右两堆合并在一起的情况

然后再注意题目中的石子是成环的，所以需要用2n的数组来存储，最后遍历也是同样。

另外dp[i][i]这种单一数组的分数是0，所以dp2数组决不能一开始fill成inf，只能在一个具体的定义下设为inf，具体看代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf=<<;

const int maxn=;

const double pi=acos(-);

const int mod=1e9+;

int a[maxn],sum[maxn];

int dp1[maxn][maxn],dp2[maxn][maxn];

int d(int x,int y){

    return sum[y]-sum[x-];

}

int main(){

    int n;scanf("%d",&n);

    //fill((int *)dp2,(int *)dp2+maxn*maxn,inf);

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

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

    a[i+n]=a[i];

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

    }

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

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

    }

    for(int len=;len<=n;len++){

        for(int l=;(l+len-)<=*n;l++){

            int r=l+len-;

            dp2[l][r]=inf;

            for(int k=l;k<r;k++){//注意k是比r小的，因为是左边是l到k，右边是k+1-r

                dp1[l][r]=max(dp1[l][r],dp1[l][k]+dp1[k+][r]+d(l,r));

                dp2[l][r]=min(dp2[l][r],dp2[l][k]+dp2[k+][r]+d(l,r));

            }

        }

    }

    int mx=,mn=inf;

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

        mx=max(mx,dp1[i][i+n-]);

        mn=min(mn,dp2[i][i+n-]);

    }

    cout<<mn<<endl<<mx<<endl;

    return ;

}

巴特西

区间DP经典石子合并

最新文章

热门文章

巴特西

区间DP经典 石子合并

最新文章

热门文章

区间DP经典石子合并