洛谷 P2300 合并神犇 题解【DP】【递推】【贪心】

作者: wjyyy 分类: DP,解题报告,贪心,递推 发布时间: 2018-06-08 16:59

点击量:28

   表面\(O(N^2)\),随机数据能让\(200000\times 200000\)过的玄学题……

题目背景

loidc来到了NOI的赛场上,他在那里看到了好多神犇。

题目描述

神犇们现在正排成一排在刷题。每个神犇都有一个能力值\(p[i]\)。loidc认为坐在附近的金牌爷能力参差不齐非常难受。于是loidc便想方设法对神犇们进行人道主义合并。

loidc想把神犇的能力值排列成从左到右单调不减。他每次可以选择一个神犇,把他合并到两侧相邻的神犇上。合并后的新神犇能力值是以前两位犇的能力值之和。每次合并完成后,被合并的两个神犇就会消失。合并后的新神犇不能再分开(万一他俩有女朋友咋办)因此每次合并后神犇的总数会减\(1\)。

loidc想知道,想治好他的强迫症需要合并多少次。

输入输出格式

输入格式:

第一行一个整数\(n\)。

第二行\(n\)个整数,第\(i\)个整数表示\(p[i]\)。

输出格式:

loidc需要合并的次数。

输入输出样例

输入样例#1:
 
8
1 9 9 4 1 2 2 9
输出样例#1:
3

说明

对于\(50\%\)的数据,\(0<n\le 5000\)。

对于\(100\%\)的数据,\(0<n\le 200000,0<p[i]\le 2147483647\),\(p\)均为随机生成。

题解:

   我们首先来看一种贪心算法:就像P1094 纪念品分组一样,从前往后遍历。我们用下界\(down\)来存满足当前单调性的最小值,例如数列\(\{1,5,6,6,7,8\}\)中,\(down\)就是\(8\)。如果有一个数使当前不满足单调性,先不让它合并,记录到一个\(tmp\)里,直到\(tmp\ge down\),\(tmp\)加了\(t\)个数,合并次数就是\((t-1)\)。但是会有一些极端情况,比如\(\{3,2,2,2,6\}\),这种贪心会把神犇们合成为\(\{3,4,8\}\),而这组神犇有更优的合成方法,就是\(\{3,6,6\}\)。

   所以这样贪心是不对的,我们应该用一种动态规划(实则为贪心+递推)的思想,求出当前决策的最优解。

   我们先预处理出前缀和\(b[i]\)数组。对于上面的反例,我们可以倒着推一下。一个数\(i\)的状态从它前面的\(j\)转移过来,当\(\sum_{k\in (j,i]}p[k]\)的和\(\ge down[j]\)时,就说明满足单调性,合并次数是\((i-j-1)\),这段代码是这样的:

 for(int j=i-1;;j--)
    if(b[i]-b[j]>=down[j])
    {
        down[i]=b[i]-b[j];
        f[i]=f[j]+i-j-1;
        break;
    }

   那这样为什么是正确的呢?我们看到,每个数i都会合成到它前面的数上去,或者自己单独罗列出来。两种状态可以转化为一种,就是合成到这个数前面的\(k\)个数上,\(k\in [0,i)\),单调性是满足的,对于这个转移方程,我们发现,对于每个\(i\),\(f[i]=f[j]+i-j-1\),其中\(i-1\)是定值,我们只要使\(f[j]-j\)尽可能小。而对于\(f[j]\)的大小,我们可以从数列中的“累加法”看出,对于从\(f[0]\)转移过来的状态\(f[1]\),是\(f[1]=i-1\),依次根据这个贪心向后递推。每次加上的附加值有一个固定的\(i-1\),这个我们无法控制,是一定存在的。而我们所能控制的是\(j\),转移方程中的\(j\)是负数,所以我们要让\(j\)尽可能大。这样才能使\(f[i]\)尽可能小。

   同时,对于\(down\),在同一个点,满足单调性的情况下,当合成次数越小时,\(down\)就会越小。【贪心】;所以我们的枚举顺序是从后往前的:根据上一段中对\(j\)的描述,让\(j\)尽可能大,所以枚举到第一个满足条件的情况,就是当前状态转移过来的最优解,我们可以直接把它break掉。补充说明:如果不break,对于更前面的点不满足当前子问题下的最优解,\(down\)数组也会随之增大。200000的数据也会因此过不了

 


tips:因为每个状态的来源只有一个,所以这个题的做法更像是利用了贪心的递推,同时无后效性。

      注意前缀和\(b\)和下界\(down\)要开long long

      严格复杂度为\(O(N^2)\)


 

Code:

#include<cstdio>
#include<cstring>
int a[200200];
int f[200200];
long long b[200200];
long long down[200200];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=b[i-1]+a[i];//前缀和处理
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i-1;;j--)
            if(b[i]-b[j]>=down[j])//非严格单调性条件
            {
                down[i]=b[i]-b[j];
                f[i]=f[j]+i-j-1;
                break;//剪枝
            }
    }
    printf("%d\n",f[n]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */