P4544，写的时候觉得有决策单调性就直接用一个变量维护当前决策扫过去，然后AC了，后来发现所有题解都是用单调队列维护的决策。

这样维护决策和单调队列的时间复杂度是一样的，但是正确性不确定，我自己证的比较感性。

想知道到这样写有没有错误啊？如果没有那就不需要单调队列吧？或者数据水了？其实用一个变量维护是错的？蒟蒻太菜了，有没有神犇看看啊！证明正确性或者浇浇我为什么没有决策单调性。（比如给个小点的hack啥的？）（拜谢）

蒟蒻的感性证明：所有物品的体积都是1，合法的情况下（到每家店买的量都不超过库存）到i为止买的总量越多，在1到(i-1)买的就越多吧（只考虑从1到i，最优决策中“在1到(i-1)买的量”随着“1到i买的总量”增加而不减）

代码：（当作有单调性写出来的，AC了，但不知道是不是对的）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10010;
int k,e,n;
ll f[505][N];//f[i][j]表示考虑到第I家商店 已经有J吨饲料的最小花费
struct node
{
    int x,f,c;
    bool operator<(const node &t)const{return x<t.x;}
}p[N];
inline ll get(int t,int i,int j)
{
    return f[t-1][j]+1ll*p[t].c*(i-j)+1ll*j*j*(p[t].x-p[t-1].x);
}
int main()
{
    scanf("%d%d%d",&k,&e,&n);
    for(int i=1;i<=n;i++) 
        scanf("%d%d%d",&p[i].x,&p[i].f,&p[i].c);
    p[++n]={e,0,0};
    sort(p+1,p+n+1);
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0,pos=0;j<=k;j++)
        {
            while(pos<j-p[i].f) pos++;
            while(pos<j&&get(i,j,pos)>=get(i,j,pos+1)) pos++;
            f[i][j]=get(i,j,pos);
        }
    printf("%lld\n",f[n][k]);
    return 0;
}

代码里pos存的是上次(j还是j-1的时候）取到最优解的时候在 1到(i-1) 买的数量