Hdu3507 (slope DP entry)

​ ​ Topic link ​​

Reference from ：​​ Blog 1​​ ​​ Blog 2​​

Look at two monotonous queue maintenance dp Introductory questions ：

​​ Beacon transmission ​​ 

​​ Blog ​​

The characteristics of this type of question ： Divide into consecutive segments The shortest segment length is k, Transmitted by beacon fire dp：f[i]=min{f[k]}(i-m<=k<=i-1)+w[i]

Maintain incremental with monotonic queues f[i], Every time you take the first place in the team .

Look again. HDU3507 The meaning of the question ：

The question :

Here you are. n Number , Ask you how to output in sequence , Minimize the total value .

The value calculation formula of each line is shown in the figure above , You can enter any character in each line here , You can put n Any character （ But in order ） Output to different lines ,

In fact, it is similar to cutting cake , Here you are. n A string , Ask you how to cut in the middle , You can cut any knife , Minimize the total value

It is also a continuous segment , But Duan Chang didn't ask .

The weight of each segment is ：（ Suppose this paragraph is k)

set up dp[i] For the former i The minimum value of the number .

So the transfer equation ：

Obviously, we can't simply use the monotonic queue optimization above .

Consider slope optimization , The optimization process is a little complicated and difficult to write , I don't have to write it myself , Here are the screenshots of the blog source ：​​ Blog ​​

Log in and copy

       

        #include 
        <
        cstdio
        >
        
#include 
        <
        cstring
        >
        
#include 
        <
        cstdlib
        >
        
#include 
        <
        algorithm
        >
        
#include 
        <
        queue
        >
        
#include 
        <
        vector
        >
        
#include 
        <
        string
        >
        
#define inf 0x3f3f3f3f
        
#define inf64 0x3f3f3f3f3f3f3f3f
        
using namespace std;
        
const int maxn = 5e5 + 10;
        

        
int que[maxn], dp[maxn];
        
int sum[maxn];
        
int n, m;
        

        
int up(int i,int j)
        
{
        
    return dp[i]+sum[i]*sum[i] - (dp[j]+sum[j]*sum[j]);
        
}
        

        
int down(int i,int j)
        
{
        
    return 2*(sum[i]-sum[j]);
        
}
        

        
int DP(int i,int j)
        
{
        
    return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
        
}
        

        
int main()
        
{
        
    while(scanf("%d%d",
        &n,
        &m)!=EOF)
        
    {
        
        sum[0] = dp[0] = 0;
        
        for (int i = 1; i 
        <
        = 
        n; 
        i++) 
        

        scanf(
        "%d"
        , 
        &sum[i]), 
        sum[i] 
        += 
        sum[i 
        - 
        1];
        

        

        int 
        tail = 
        0, 
        head = 
        0;
        

        que[tail++] = 
        0;// Because it may be the front i All of them as a segment is the minimum 
        

        for 
        (int 
        i = 
        1; 
        i 
        <= n; i++) {//head+1
        <
        tail 
         Ensure that there are at least two values in the queue 
        

        while(head+1
        <tail
        &
        &up(que[head+1],que[head])
        <
        =
        sum[i]*down(que[head+1],que[head])) 
        head++;
        

        //head+1 Than head better 
        

        dp[i] = 
        DP(i, 
        que[head]);
        

        while 
        (head+1
        <tail
        &
        &up(i,que[tail-1])*down(que[tail-1],que[tail-2])
        <
        =
        up(que[tail-1],que[tail-2])*down(i,que[tail-1])) 
        tail--;
        

        // Maintenance pocket , Convex hull has been proved to be inconsistent in the middle 
        

        que[tail++] = 
        i;
        

        

        }
        

        printf(
        "%d\n"
        , 
        dp[n]);
        

        }
        

        return 
        0;
        

        }
        

        

        ————————————————
        

         Copyright notice ： This paper is about CSDN Blogger 「ccsu_deer」 The original article of , follow CC 
        4.0 
        BY-SA Copyright agreement , For reprint, please attach the original source link and this statement .
        

         Link to the original text ：https://blog.csdn.net/qq_41286356/article/details/106267614
       
       

        
1.
        
2.
        
3.
        
4.
        
5.
        
6.
        
7.
        
8.
        
9.
        
10.
        
11.
        
12.
        
13.
        
14.
        
15.
        
16.
        
17.
        
18.
        
19.
        
20.
        
21.
        
22.
        
23.
        
24.
        
25.
        
26.
        
27.
        
28.
        
29.
        
30.
        
31.
        
32.
        
33.
        
34.
        
35.
        
36.
        
37.
        
38.
        
39.
        
40.
        
41.
        
42.
        
43.
        
44.
        
45.
        
46.
        
47.
        
48.
        
49.
        
50.
        
51.
        
52.
        
53.
        
54.
        
55.
        
56.
        
57.
        
58.