【DP合集】合并 union

给出一个 1 ∼ N 的序列 A ( A 1 , A 2 , ..., A N ) 。你每次可以将两个相邻的元素合并，合并后的元素权值即为这两个元素的权值之和。求将 A 变为一个非降序列，最少需要多少步操作。

Input

输入的第一行一个整数 N ( N ≤ 5000) 。
接下来一行 N 个整数，描述序列 A 。保证序列 A 中的每个元素的值不超过 1000 。

Output

输出一行一个整数，表示最少的操作数。

题解：

区间dp真的难，(｡･∀･)ﾉﾞ嗨！

好了，设dp[i][j]表示从区间把前j个数，把区间i~j合并后满足单调的元素数量，我们可以考虑，统计一个前缀和sum，然后枚举

三个端点i,j,k,我们是想把i~j压缩成一个数，然后k在i之前，找到元素数量最少的，进行转移，转移条件是sum[i]-sum[k-1]<=sum[j]-sum[i]

代码：

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<algorithm>

#include<cstring>

const int MAXN=;

using namespace std;

int dp[MAXN][MAXN],sum[MAXN],ans=-;

void cl(){

    memset(dp,,sizeof(dp));

    memset(sum,,sizeof(sum));

}

int main(){

    cl();

    int n;

    scanf("%d",&n);

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

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

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

    }

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

        dp[i][]=;

        int k=i,res=-;

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

            while(k&&sum[i]-sum[k-]<=sum[j]-sum[i]) res=max(res,dp[i][k--]);

            if(res==-) dp[j][i+]=-;

            else dp[j][i+]=max(dp[j][i+],res+);

            //printf("i=%d j=%d k=%d\n",i,j,k);

        }

    }

    for(int i=;i<=n;i++) ans=max(ans,dp[n][i]);

    if(ans==-) printf("-1");

    else printf("%d",n-ans);

}

巴特西

【DP合集】合并 union

Input

Output

最新文章

热门文章