subject

This problem can be seen from the beginning as a dynamic programming problem , But I don't know how to write the state transition equation , But we can think about it. It should be an interval DP, And the interval DP The characteristic of state transition equation is that the state transition equation is generally related to the left node and right node or the middle breakpoint of the interval , Because we choose one of two points at a time, and the one in the original question a The value is (n-(left-right)), So we can get the state transfer equation

dp[i][j]=max(dp[i][j-]+data[j]*(n-(j-i)),dp[i+][j]+data[i]*(n-(j-i)));

That's the end of it , Of course not. , First we need to preprocess out dp[i][i]=data[i]

And then we look at the equation , There's a problem with the equation j The first one in the class and i It's the last one who pushed it out , So we're going to let i Push back and forth ,j Push from the front to the back . So this question gives us an inspiration , It's not enough just to get the state transfer equation , It's also important how you push .

Code :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int data[],dp[][],maxn=;
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&data[i]),dp[i][i]=data[i];
for(int i=n;i>=;i--)
{
for(int j=i;j<=n;j++)
dp[i][j]=max(dp[i][j-]+data[j]*(n-(j-i)),dp[i+][j]+data[i]*(n-(j-i)));
}
cout<<dp[][n];
return ;
}

Luogu P2858 Dairy snacks More related articles on the solution of the problem

  1. Luogu P2858 Dairy snacks Answer key Section DP Introductory questions

    The main idea of the topic : John often gives special allowance to cows with high milk yield , So soon the cows had a lot of money they didn't know how to spend . So , John bought \(N(1 \le N \le 2000)\) A delicious snack to sell to the cows . Every day John sells a zero ...

  2. [ Luogu p2858] Dairy snacks

    Topic link : Am I Topic analysis : What is it? , Section dp Do you ? How come everyone is talking about interval dp The appearance of The end zone dp I don't know what it is quq So he used the metaphysical posture A After this question set up dp[i][j][0] It means the first one i God , On the left, I chose j individual , When ...

  3. Luogu P2858 Dairy snacks

    https://www.luogu.org/problemnew/show/P2858 There is no doubt that dp. ![ Section dp introduction ] We define dp[i][j] From i To j The biggest benefit of , Obviously we need to use smaller ...

  4. Section DP Luogu P2858 Milk snacks

    Topic link The question : Do you have n Two goods from 1-n Arrange in sequence , You can choose one from both sides every day , The selling price is the number of days of the day multiplied by the initial price of the goods , Ask the maximum price of the goods sold out Input : first line n, And then n The initial value of the goods This problem can't be solved by greed ...

  5. Luogu P1578 Dairy bathing place Answer key

    Topic 1. The effective sub rectangle is defined as a sub rectangle whose inner part does not contain any obstacle points and whose boundary is parallel to the coordinate axis . As shown in the figure , The first is the effective subrectangle ( Despite the obstacles on the border ), The second is not a valid subrectangle ( Because there are obstacles inside ). 2. Maximal efficient subrectangles : An effective ...

  6. Luogu P2402 Cows hide

    Luogu P2402 Cows hide Background This is a very simple question , However, the cows have been very confused because of the rain , Can't do this calculation , So the task is up to you .( The reason for the confusion of cows is described in the title ) Title Description There are... On a farm n A field . ...

  7. Luogu 2344 Cows protest (DP+BIT+ discretization )

    Luogu 2344 Cows protest Address :http://www.luogu.org/problem/show?pid=2344 Background Generic Cow Protests, 2011 Feb Title Description ...

  8. Luogu P2832 On the road to analysis + Solution code 【 Metaphysics is the shortest path 】

    Luogu P2832 On the road to analysis + Solution code [ Metaphysics is the shortest path ] Background : Small X Came to the mountains , Enjoy the pleasure of mountains and forests . When he is happy to forget his worries , He suddenly found out , The beginning of school is imminent Title Description : In the mountains n A mountain . Between the mountains there is m It's a small path , Each one connects two ...

  9. 【 Luogu P3960】 Line up to solve the problem

    [ Luogu P3960] Line up to solve the problem Topic link The question : Sylvia  A girl who loves learning . Some time ago ,Sylvia  Took part in the military training of the school . as everyone knows , We need to stand in a square array during military training . Sylvia There are  n×m ...

Random recommendation

  1. Java Thread join() Usage of

    Java Thread in , join() Method is mainly to change the calling method thread complete run After the contents of the method , In execution join() Method . Example : class ThreadTesterA imple ...

  2. linux How to deal with the lack of command execution authority in

    stay linux If you don't have enough authority to execute the command, you need to increase the authority , Let's see what happens first Check permissions Then give authority Carry out orders

  3. How to judge radio button radio To be selected

    Today, I'm going to write a radio button to show some content after selecting it , The first problem is how to get the value in the election ! html The code is as follows <input class="joined" type="radio&q ...

  4. PHP Get the user's reality IP , TaoBao IP Interface to get ip Location ( turn )

    <?php /** * Get the user's reality IP */ function getIP() { static $realip; if (isset($_SERVER)){ if (isset($_SER ...

  5. Make for yourself Linux Small system

      One . Preface Linux Operating system to 1991.10.5 Since the birth of the U.S , Because of its open source and freedom, it has won the favor of many technology giants , Every Linux Fans have contributed their part to it , No matter what Linux Kernel or open source software, etc , All for ...

  6. table Word wrap

    <table border=" align="center" style="table-layout:fixed;word-wrap:break-word ...

  7. Chat PHP Private components and how to create your own PHP Components ( turn )

    1. Private components Most of the time we use open source components that are publicly available , But sometimes if a company uses internally developed PHP Components , And it can't be open source based on license and security issues , You need to use private components . Yes Composer for , It's a piece of cake . ...

  8. The blueprint Tips

    There are some useful nodes , Don't write it down , It's easy to forget . 1. Call the command line 2. Play the video After playing, you need to play a short segment to pause !

  9. The front-end study ——jquery Operation example

    One .jquery and DOM Function conversion . jquery convert to dom $(] . dom convert to jquery var i1=documen.getElementById('#i1')---------> ...

  10. nodejs waterfall Use

    waterfall(tasks, [callback]) ( Multiple functions are executed in turn , And the output of the former is the input of the latter ) Execute multiple functions in sequence . The value produced by each function , Will pass to the next function . If something goes wrong in the middle , Later functions will ...