P2616 [USACO10JAN] Buying Feed, II S

题目描述FJ 开车来到镇上他要带KKK吨饲料回家。运送饲料是需要花钱的如果他的车上有XXX吨饲料开车DDD公里就需要D×XD×XD×X元。FJ 可以从NNN家商店购买饲料所有商店都在一个坐标轴上第iii家店的位置是XiX_iXi​饲料的售价为每吨CiC_iCi​元库存为FiF_iFi​。这个镇上有N(1≤N≤100)N(1 \le N \le 100)N(1≤N≤100)家商店编号为1∼N1 \sim N1∼N售卖饲料所有商店都在一个长度为E(1≤E≤350)E(1 \le E \le 350)E(1≤E≤350)的XXX轴上。第iii个商店位于数轴上XiX_iXi​的位置最多可以售卖给 FJFi(1≤Fi≤100)F_i(1 \le F_i \le 100)Fi​(1≤Fi​≤100)吨饲料花费为Ci(1≤Ci≤106)C_i(1 \le C_i \le 10^6)Ci​(1≤Ci​≤106)元每吨。奇妙的是XXX轴上同一个坐标可能不只有一家商店。FJ 从坐标为000的地方出发并且只能向前走直到到达坐标为EEE的地方并且需要买到KKK吨饲料。他可以在沿途任意一家商店停下来买饲料。请你求出 FJ 购买并运输KKK吨饲料的最小花费是多少。输入格式第一行三个整数KKKEEE和NNN1≤K≤1001\leq K \leq 1001≤K≤1001≤E≤3501\leq E \leq 3501≤E≤3501≤N≤1001\leq N \leq 1001≤N≤100第二行到第N1N 1N1行第i1i 1i1行有三个整数XiX_iXi​FiF_iFi​和CiC_iCi​0XiE0 X_i E0Xi​E1≤Fi≤1001\leq F_i \leq 1001≤Fi​≤1001≤Ci≤1061\leq C_i \leq 10^61≤Ci​≤106。输出格式一个整数表示购买并运送饲料的最小花费。输入输出样例 #1输入 #12 5 3 3 1 2 4 1 2 1 1 1输出 #17说明/提示在离家较近的两家商店里各购买一吨饲料则花费路上的钱是123123123花在店里的钱是224224224。思路简单贪心按照每家店的饲料的单价原单价加与EEE的距离排序。代码#includebits/stdc.husingnamespacestd;structdid{intx,f,c,d;}a[101];intn,k,e,cnt,ans;boolcmp(did x,did y){returnx.dy.d;}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinken;for(inti1;in;i){cina[i].xa[i].fa[i].c;a[i].d(e-a[i].x)a[i].c;//其实 d 是多余的直接在 c 上加即可}sort(a1,a1n,cmp);for(inti1;in;i){if(cnta[i].fk){ansa[i].d*(k-cnt);break;}else{ansa[i].d*a[i].f;cnta[i].f;}}coutans;return0;}