P4544 [USACO10NOV]购买饲料Buying Feed
约翰开车来到镇上，他要带KK吨饲料回家。运送饲料是需要花钱的，如果他的车上有XX吨饲料，每公里就要花费 X 2 X^2 X2 元，开车D公里就需要 D × X 2 D\times X^2 D×X2 元。约翰可以从N家商店购买饲料，所有商店都在一个坐标轴上，第ii家店的位置是 X i X_i Xi​​ ，饲料的售价为每吨 C i C_i Ci​ 元，库存为 F i F_i Fi​ 。

约翰从坐标X=0开始沿坐标轴正方向前进，他家在坐标X=E上。为了带K吨饲料回家，约翰最少的花费是多少呢？假设所有商店的库存之和不会少于K。

举个例子，假设有三家商店，情况如下所示：

坐标 X=1 X=3 X=4 E=5
库存 1 1 1
售价 1 2 2
如果K=2，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是1+4=5，花在商店的钱是2+2=4，共需要9元。

输入格式
第1行:三个整数K,E,N 第2…N+1行:第i+1行的三个整数代表, X i , F i , C i X_i,F_i,C_i Xi​,Fi​,Ci​
输出格式
一个整数,代表最小花费
输入

2 5 3
3 1 2
4 1 2
1 1 1

输出

9

说明/提示
1 ≤ K ≤ 10000 , 1 ≤ E ≤ 500 , 1 ≤ N ≤ 500 1\leq K \leq10000,1 \leq E \leq 500 , 1 \leq N \leq 500 1≤K≤10000,1≤E≤500,1≤N≤500
1 ≤ F i ≤ 10000 , 1 ≤ C i ≤ 1 0 7 1 \leq Fi \leq 10000, 1 \leq C_i \leq 10^7 1≤Fi≤10000,1≤Ci​≤107

容易推出，先对x排序，前i个store买了j吨商品：dp[i][j]

d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ z ] + z 2 d x + f i ( j − z ) ) dp[i][j]=min(dp[i-1][z]+z^2dx+f_i(j-z)) dp[i][j]=min(dp[i−1][z]+z2dx+fi​(j−z))， 0 < = ( j − z ) < = c i 0<=(j-z)<=c_i 0<=(j−z)<=ci​
， z < = j z<=j z<=j

这样是O(nkf)的

也就是多重背包可以用多个01背包暴力出来

我们知道，任意一个整数都能用若干个互不相同的 2 i 2^i 2i表示出来，

令 P = 2 0 + 2 1 + 2 2 + ⋯ + 2 i + r P=2^0+2^1+2^2+\dots+2^i+r P=20+21+22+⋯+2i+r，且 r < 2 i + 1 r<2^{i+1} r<2i+1

所以，1至 ( 2 i + 1 − 1 ) (2^{i+1}-1) (2i+1−1)之间的数都能用若干个互不相同的 2 i 2^i 2i表示出来，
同时加上r，
r+1至 ( r + 2 i + 1 − 1 ) = P (r+2^{i+1}-1)=P (r+2i+1−1)=P也能表示出来，且每个数最多用一次
这样，p重背包能转化成log§个01背包。
在进行暴力01即可。复杂度降到了O(nk*log(f))

#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool read(T &x){
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
    return true;
}
template<class T>inline void print (T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print (x/10);
    putchar('0'+x%10);
}
#define read(a,b) read(a),read(b)
#define read(a,b,c) read(a),read(b),read(c)
#define Init(a,v) memset(a,v,sizeof(a))
typedef long long ll ;
const ll MAXN=508,inf=0x3f3f3f3f,mod=1e9+7;
ll k,e,n;
struct S{
    ll x,f,c;
    bool operator<(const S&o)const{return x<o.x;}
}s[MAXN],t[MAXN*15];
ll dp[MAXN*20],cnt;
int main() {
    read(k,e,n);
    for(ll i=1;i<=n;++i)read(s[i].x,s[i].f,s[i].c);
    sort(s+1,s+n+1);//x不是递增的
    for(ll i=1;i<=n;++i){//将1~n个多重背包变成1~cnt个01背包。
        for(ll j=1;j<=s[i].f;j<<=1){
            t[++cnt].c=s[i].c*j;
            t[cnt].x=s[i].x;
            t[cnt].f=j;
            s[i].f-=j;
        }
        if(s[i].f){//如果有r
            t[++cnt].x=s[i].x;
            t[cnt].f=s[i].f;
            t[cnt].c=s[i].c*s[i].f;
        }
    }
    t[0].x=t[1].x;//第1个商店与上一个距离为0.
    Init(dp,inf);
    dp[0]=0;
    for(ll i=1;i<=cnt;++i){
        for(ll j=k;j>=t[i].f;--j){//01背包滚动数组
            dp[j]=min(dp[j]+(t[i].x-t[i-1].x)*j*j,
                      dp[j-t[i].f]+(t[i].x-t[i-1].x)*(j-t[i].f)*(j-t[i].f)+t[i].c);
        }
    }
    printf("%lld",dp[k]+(e-s[n].x)*k*k);//从最后一个商店到e
    return 0;
}