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<stdio.h> #include<string.h> #include<algorithm> #define MAXN 510 #define MAXK 10010 #define INF 0x3f3f3f3f3f3f3f3fll typedef 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; }