BZOJ_2059

    本来打算想想费用流的，但是既然给的是直线，八成就是让dp了，否则完全可以给成图的。

    不妨用f[i][j]表示递推到第i个商店时，在前i-1个商店一共买了j的饲料，这样就有状态转移方程f[i][j]=min{f[i-1][k]+(j-k)*C[i-1]}+j*j，其中0<=j-k<=F[i-1]。这样裸着做的话，复杂度是没法承受的，但如果把min{}里的j拿出来的话就会得到f[i][j]=min{f[i-1][k]-k*C[i-1]}+j*C[i-1]+j*j，这样min里面的只和k有关，而且k是要满足一定范围的，这时我们可以用单调队列来维护f[i-1][k]-k*C[i-1]的最小值，这样每次决策就是O(1)了。

#include
     
      #include
      
       #include
       
        #define MAXN 510#define MAXK 10010#define INF 0x3f3f3f3f3f3f3f3flltypedef long long LL;struct Shop{    int x, c, f;    bool operator < (const Shop &t) const    {        return x < t.x;    }}shop[MAXN];int N, E, K, q[MAXN];LL f[MAXN][MAXK];void init(){    for(int i = 0; i < N; i ++)        scanf("%d%d%d", &shop[i].x, &shop[i].f, &shop[i].c);    std::sort(shop, shop + N);}void solve(){    for(int i = 0; i <= N; i ++)        for(int j = 0; j <= K; j ++) f[i][j] = INF;    f[0][0] = 0;    shop[N].x = E;    for(int i = 1; i <= N; i ++)    {        int front = 0, rear = 0;        for(int j = 0; j <= K; j ++)        {            while(front < rear && j - q[front] > shop[i - 1].f) ++ front;            if(f[i - 1][j] != INF)            {                while(front < rear)                {                    int k = q[rear - 1];                    if(f[i - 1][k] - (LL)k * shop[i - 1].c < f[i - 1][j] - (LL)j * shop[i - 1].c) break;                    -- rear;                }                q[rear ++] = j;            }            if(front < rear)            {                int k = q[front];                f[i][j] = f[i - 1][k] + (LL)(j - k) * shop[i - 1].c + (LL)j * j * (shop[i].x - shop[i - 1].x);            }        }    }    printf("%lld\n", f[N][K]);}int main(){    while(scanf("%d%d%d", &K, &E, &N) == 3)    {        init();        solve();    }    return 0;}