"POJ 3666" Making the Grade problem solution (two methods)

0前言

感谢yxy童鞋的dpand violent practices！

1 算法标签

优先队列、dp动态规划+滚动数组优化

2 题目难度

提高/提高+

CF rating：2300

3 题面

「POJ 3666」Making the Grade 路面修整

4 分析题面

4.1 简要描述

给出数列 \(A\), 求非严格单调不上升或单调不下降, 且\(S=\sum^N_{i=1}|A_i-B_i|\) 最小的序列\(B\),输出\(S\)

4.2 模型转换

输入\(N\), 然后输入\(N\)个数,求最小的改动这些数使之成非严格递增或非严格递减即可

5 问题分析

以B为非严格单调递增为例

5.0 暴力

We directly consider that we have chosen\(n\)个数：

• 若\(n=1,A_1=B_1\)时S最小为\(|A_1-B_1|\)

• 若\(n>1\),前面已经选择了n-1个数,取得了最小值,考虑怎么取第n个数

  • 若 \(A_i≥B_{i-1}\),\(B_i=A_i\)显然最优

  • 若\(A_i< B_{i-1}\)

    • \(B_i=A_i\)

    • 将\(B_k,B_{K+1},...,B_i\)都赋值为\(A_k,A_k+1,...,A_i\)的中位数

    口胡证明：

    我们可以将\(B_k,B_{K+1},...,B_i\)标记在数轴上

    再将\(A_k,A_k+1,...,A_i\)标记上

    那么,其实S的几何含义就是每一组\(A_i\)到\(B_i\)的距离之和

    Our elementary school math also learned the absolute value most value problem：

    求\(|x-k_1|+|x-k_2|+|x-k_3|...\)的最小值

    其实和这里的\(S\)是没有任何区别的

    所以,We know that the zero-point segmentation method can solve this kind of problem

    就是取中位数（就是使每个绝对值内部为0的x答案数组的中位数）

    可以使得绝对值之和最小

    

  1. 如果\(x\)在两个\(k\)之间,那么无论\(x\)在哪,距离之和都是这两个\(k\)的距离

  2. 如果在这两个\(k\)之外,那么距离之和则为两个\(k\)距离加上两倍的\(x\)距近的\(k\)的距离,certainly not better than the first case

     那么我们只要尽量让\(x\)在越多的\(k\)之间即可

     Then the best solution\(x\)在图中就是\(4\),如果\(k\)的个数为偶数\(n\),则是\(k_{n/2}和K_{n/2+1}\)之间

     综上,选择中位数最佳

5.1 法一 dp（动态规划）

通过综上分析(5.0中),We definitely can't do a direct violent simulation.（这个复杂度直接爆掉了）

但是！

we can get a\(very\) \(important\)的结论：

\(B\)数列中的每个数必定都为\(A\)数列中的元素

所以,我们可以考虑用\(dp\)来解决：

阶段：到第\(i\)位

状态：\(dp_{i,j}\)表示以\(B_j\)结尾的\(S_{min}\)

B数组是A的复制排序处理过后的数组

$\space \space $ \(dp[i][j]\)表示把前i个数变成不严格单调递增且第\(i\)个数变成原来第\(j\)大的数的最小代价

转移方程：\(dp_{i,j}=min(dp_{i-1,k})+|A_i-B_j|,其中1≤j≤n,1≤k≤j\)

5.2 法二 堆（优先队列）

5.2.1 内心思考

Now we can think again,Since it is necessary to seek non-strictly monotonically increasing,So what's important？

当前序列的最大值.（That should be for sure）

最大值？

Do you have any weird ideas?？

...

堆！

So just make a big pile！

5.2.2 模拟过程

begin...

$\space \space \space \space \space \space $数据 ：1 3 2 4 5 3 9

i=1:

\(\space \space \space \space \space\) 堆：空,a[i]=1,top=空

At this point the heap is empty,sure to put in

\(\space \space \space \space \space \space\)∴把a[i]放入堆中

\(\space \space \space \space \space \space\)->堆：1 ,a[i]=1,top=1

i=2:

\(\space \space \space \space \space \space\)堆：1 ,a[i]=3,top=1

这个时候a[i]>top,It means that the non-strict monotonically increasing

\(\space \space \space \space \space \space\)∴把a[i]放入堆中

\(\space \space \space \space \space \space\)->堆：3 1 ,a[i]=3,top=3

i=3:

\(\space \space \space \space \space \space\)堆：3 1 ,a[i]=2,top=3

这个时候a[i]<top,It means that the non-strict monotonic increase is no longer satisfied.,那么就需要修改top或者是a[i]的值

The most economical method will definitely costtop-a[i]来进行更改

After changing you will get(a[i],a[i]),(a[i]+1,a[i]+1)....(top-1,top-1),(top,top)这些二元组

There must be a valid binary in there,It's definitely illegal

introduce another variable：newtop:当前top被popafter fallingtop

我们可以肯定,Among all the dyads above,is there a value that can be satisfied≥newtop的,So this pair of tuples must satisfy non-strictly monotonically increasing,Then the following data only needs to satisfy the numerical value≥newtop就可以了

So we need to make this pair of binary values ​​as little as possible without affecting the subsequent operations,Then put the two minimum values,即a[i].

\(\space \space \space \space \space \space\)∴把top给pop掉,a[i]和a[i]放入堆中

\(\space \space \space \space \space \space\)->堆：2 2 1 ,a[i]=2,top=2

This time put twoa[i]是合法的,Then we will see one into twoa[i]不合法的情况

...

i=6

\(\space \space \space \space \space \space\)堆：5 4 2 2 1 ,a[i]=3,top=5

After doing what we discussed earlier,会是

\(\space \space \space \space \space \space\)堆：4 3 3 2 2 1 ,a[i]=3,top=4

\(\space \space \space \space \space \space\)原序列: 1 2 2 4 3 3

At this time, we can find that if thea[5]改成3,Looks illegal in the original sequence,But is this a big problem?？

不大.

Because our changed binary is not necessarily non-3 3,它也可以是4 4,5 5,then it's legal,我们把3The reason for throwing it in is to try not to affect subsequent operations.,Let the changes in the future be as small as possible,Better maintenance of non-strictly monotonically increasing

5.2.3 总结

也就是说,我们需要明确,The heap may not store the final sequence,It stores the minimum value that the current sequence needs to satisfy.

Just look at a picture,understand the correctness...：

6 实现细节

6.1 法一：dp（动态规划）

6.1.1 滚动数组

从我们的\(dp\)方程：\(dp_{i,j}=min(dp_{i-1,k})+|A_i-B_j|,其中1≤j≤n,1≤k≤j\)

Gray is often easily widened to calculate the space complexity is\(O(n^2)\)

这个..Adhering to the us能省则省的原则

see this open 2d array\(O(n^2)\)Seems a bit of a waste of space

So how to optimize the space?？

and because of our\(dp\)only used in the equation\(i-1\)的信息

So we react subconsciously：

——用滚动数组优化！

\(\space \space\)用位运算符&来记录,这样就只用了\(0/1\)来表示

重复利用,节省空间

\(\space\space\space\space\) \(i\)&\(1\)的效果和\(i\)%\(2\)的效果是一样的,但是\(i\)&\(1\)要快一点

\(\space\space\space\space\) 且这种方式比直接写\(0/1\)少了一个不断交换的过程

\(\space\space\space\space\) 窝jioStill got this thing·····香的

将\(i->i\) & \(1\),\(i-1->(i-1)\)&\(1\)

方程就变成了这样：

\(dp[i\)&\(1][j]=min(dp[(i-1)\)&\(][k])+|A[i]-B[j]|,其中1≤j≤n,1≤k≤j\)

6.1.2 最小值

但是这个复杂度..

看上去好像是3层循环,就是\(O(n^3)\)啊

在\(n<=2000\) 的时候就已经\(game\space over\)了,显然不行啊

这个xiaoThe problem should be on hand

其实只要一边更新\(min(f[i-1][k])\)一般算当前的\(f[i][j]\)就行

（因为\(k\)只到\(j\)）

6.1.3 降序

不严格单调不上升的情况也一样

更加方便的是可以把\(B\)数组从大到小排序后,做单调不下降的dp就了

6.1.4 时间复杂度

二维DP,所以就是\(O(n^2)\)

6.2 法二 堆（优先队列）

6.2.1 具体操作

Take non-strictly monotonically increasing as an example

To get a large root pile,依次遍历数组

• When the heap is empty directly\(push\)

• 当\(a[i]≥top\)的时候直接\(push\)

• 当\(a[i]< top\)的时候,ans+=top-a[i],先pop再push两次a[i]（one to replace the originalpop,一个是本身）

That's not strictly monotonically decreasing, it's the opposite.

Finally put the two\(ans\)去一个\(min\)就好了

6.2.2 时间复杂度

stack of operations,所以就是\(O(nlogn)\)

7 代码实现

7.1 法一：dp（动态规划）

#include<bits/stdc++.h>

using namespace std;

const int N=2e4+2;

int n,f[2][N],a[N],b[N],ans=0x3f3f3f3f;

bool cmp1(int x,int y){

    return x<y;

}//升序

bool cmp2(int x,int y){

    return x>y;

}//降序

void work(){

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

        f[1][i]=abs(a[1]-b[i]);

    }//边界条件

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

        int minn=f[(i-1)&1][1];

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

            minn=min(minn,f[(i-1)&1][j]);//边更新边求

            f[i&1][j]=minn+abs(a[i]-b[j]);

            //滚动数组

        }

    }

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

        ans=min(ans,f[n&1][i]);

    }//求答案

}

int main(){

    scanf("%d",&n);

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

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

        b[i]=a[i];//拷贝到b数组

    }

    sort(b+1,b+1+n,cmp1);//从小到大

    work(); //dp计算

    sort(b+1,b+1+n,cmp2);//从大到小

    work();//直接就是一样的啊

    printf("%d",ans);//输出最小

    return 0;

}

7.2 法二：堆（优先队列）

#include<bits/stdc++.h>

using namespace std;

int n;

int a[3100];

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);//读入

    priority_queue<int>q;//大根堆,Handling non-strictly monotonically increasing

    int ans=0,sum=0;

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

        if(q.empty())q.push(a[i]);//空

        else{

            if(q.top()<=a[i])q.push(a[i]);//Operation as explained above

            else{

                ans+=abs(a[i]-q.top());//plus answer

                q.pop();//弹出

                q.push(a[i]);//放入两次

                q.push(a[i]);

            }

        }

    }

    priority_queue<int,vector<int>,greater<int> >p;//小根堆,Handling non-strictly monotonically decreasing

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

        if(p.empty())p.push(a[i]);//空

        else{

            if(p.top()>=a[i])p.push(a[i]);//如上解释

            else{

                sum+=abs(a[i]-p.top());//plus answer

                p.pop();//弹出

                p.push(a[i]);//放入两次

                p.push(a[i]);

            }

        }

    }

    printf("%d",min(ans,sum));

    return 0;

}

very simple and clear

8 总结

1. 最大的收获：Even if you can't do it, you need to think about some possible ways,Maybe hit right

2. 新鲜的知识：更优秀的滚动数组写法|Wonderful Use of Heaps

3. 相似的题目：CF #371 div.1 C Sonya and Problem Wihtout a Legend

「POJ 3666」Making the Grade 题解（两种做法）的更多相关文章

1. 「ARC 139F」Many Xor Optimization Problems【线性做法,step-in】

   「ARC 139F」Many Xor Optimization Problems 对于一个长为 \(n\) 的序列 \(a\),我们记 \(f(a)\) 表示从 \(a\) select a number of,可以得到的最 ...

2. 「POJ Challenge」生日礼物

   Tag 堆,贪心,链表 Solution Condenses consecutive numbers with the same sign into one number,Remove non-positive numbers from both ends,get a sequence of alternating positive and negative,Throw the absolute values ​​of all numbers in the sequence into the heap,Subtract a minimum value from the sum of all positive numbers,The calculation of this minimum value is the same as「 ...

3. 「POJ 1135」Domino Effect（dfs）

   BUPT 2017 Summer Training (for 16) #3G 题意 There are dominoes laid outnkey card,Between two key card edge represent between them have a row of dominoes.从1The number key card began to be pushed down,Ask the last fallen card ...

4. 「POJ - 1003」Hangover

   BUPT 2017 summer training (16) #2C 题意 n个卡片可以支撑住的长度是1/2+1/3+1/4+..+1/(n+1)个卡片长度.现在给出需要达到总长度,求最小的n. 题解 ...

5. 「POJ - 2318」TOYS (叉乘)

   BUPT 2017 summer training (16) #2 A 题意 have a toy box,被npartitions are divided into left tou右n+1个区域,Then give the coordinates of each toy,Find how many toys there are in each area. 题解 Use cross product to judge toys in turn ...

6. 「POJ 2182」 Lost Cows

   题目链接 戳这 题目大意 \(N(2 <= N <= 8,000)\)头奶牛有\(1..N\)Unique brands in the range.For each cow in line,Know the number of cows ahead of that cow and smaller than that cow's brand.根据这些 ...

7. 「POJ 3268」Silver Cow Party

   更好的阅读体验 Portal Portal1: POJ Portal2: Luogu Description One cow from each of N farms \((1 \le N \le 1 ...

8. NBLLittle cute commemorative game「 第一弹 」 游记（部分题解）

   比赛链接 洛谷:Abusive games are prohibited . ??? 反正我觉得,gyx挺危险的 不说废话. 首先,比赛经验,No call for the first few hours,follow the list. 一看 T1. 发现是道水题,cut straight away. 然后看到了 T2. 感 ...

9. Solution -「POJ 3710」Christmas Game

   \(\mathcal{Decription}\)   Link.   define a christmas tree: is a cactus. There are no two points on the same ring,Degree average \(\ge 3\).   给出 \(n\) unrelated christmas tree,双人 ...

10. 「POJ 2699」The Maximum Number of Strong Kings

    题目链接 戳我 \(Describe\) A league can be represented as a complete graph,Dots indicate contestants,任意两点u, vThere is exactly one directed edge between\((u, v)\)或\((v, u)\),表示\(u\)打败\(v\)或 ...

随机推荐

1. Gson的使用

   GSON:是Google开发的Java API,用于转换Java对象和Json对象 <dependency> <groupId>com.google.code.gson< ...

2. js对象、数组转换字符串

   对象转换成字符串需要使用toString()方法. 1 var a = function(){ 2 console.log(111); 3 }; 4 var b = a.toString(); 5 c ...

3. SilverFoxServer出炉！！

   SilverFoxServer是啥?各位看官搜一下SmartFoxServer便知 是一套服务端+客户端通迅框架,快速搭建起回合制,棋牌类的联机 网页游戏 SilverFoxServer的特点包括 用 ...

4. JSP之session

   index.jsp: <form id="form1" name="form1" method="post" action=" ...

5. BP神经网络代码

   close allclear allclcload x.txt; load y.txt; inputs = x';targets = y; % 创建一个模式识别网络(两层BP网络),At the same time, the middle layer of nerve is given ...

6. Inno Setup入门（八）——有选择性的安装文件

   这主要使用[Components]段实现,一个演示的代码如下: [setup] ;全局设置,本段必须 AppName=Test AppVerName=TEST DefaultDirName=" ...

7. [POI2007]洪水pow bfs

   发现:Only building pumps in all own cities must be the optimal solution. So sort your city by height,The premise that the city does not need to be built is that starting from him, a path whose height is less than or equal to him can reach a pump that has already been built. sort+bfs...... #inclu ...

8. iis+nginx实现负载均衡

   简要说明:nginxIntroduction of Self-Baidu. 目的:Divide user requests to various servers to reduce pressure.nginxTransfer the requests of the listening port to the server where the website is deployed on average. 一.windows上安装nginx 1.官网下载windows ...

9. 学习PYTHON之路, DAY 10 进程、线程、协程篇

   线程 线程是应用程序中工作的最小单元.它被包含在进程之中,是进程中的实际运作单位.一条线程指的是进程中一个单一顺序的控制流,一个进程中可以并发多个线程,每条线程并行执行不同的任务. 直接调用 impo ...

10. 如何预览Github上的页面

    参考链接:https://www.jianshu.com/p/46ddd926f005