【洛谷P3089】 [USACO13NOV]POGO的牛Pogo-Cow

FJ给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。

FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。

每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。

设\(f(i)(j)\)表示第i个点从j转移过来的最优解，朴素\(n^3\)。

正反来两边，特判k=0；

正解单调队列优化，可是我不会。

洛谷上\(n^3\)水过。

我菜我菜。

code：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define int long longusing namespace std;const int wx=2017;inline int read(){    int sum=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}    return sum*f;}struct node{    int x,p;    friend bool operator < (const node & a,const node & b){        return a.x