Description
L 公司有 N 个工厂, 由高到底分布在一座山上如图所示, 工厂 1 在山顶, 工厂 N 在山脚由于这座山处于高原内
陆地区(干燥少雨),L 公司一般把产品直接堆放在露天, 以节省费用突然有一天, L 公司的总裁 L 先生接到气象
部门的电话, 被告知三天之后将有一场暴雨, 于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏由于
地形的不同, 在不同工厂建立仓库的费用可能是不同的第 i 个工厂目前已有成品 Pi 件, 在第 i 个工厂位置建立仓库
的费用是 Ci 对于没有建立仓库的工厂, 其产品应被运往其他的仓库进行储藏, 而由于 L 公司产品的对外销售处设
置在山脚的工厂 N, 故产品只能往山下运(即只能运往编号更大的工厂的仓库), 当然运送产品也是需要费用的,
假设一件产品运送 1 个单位距离的费用是 1 假设建立的仓库容量都都是足够大的, 可以容下所有的产品你将得到
以下数据: 1: 工厂 i 距离工厂 1 的距离 Xi(其中 X1=0);2: 工厂 i 目前已有成品数量 Pi;:3: 在工厂 i 建立仓库的费用
Ci; 请你帮助 L 公司寻找一个仓库建设的方案, 使得总的费用 (建造费用 + 运输费用) 最小
Input
第一行包含一个整数 N, 表示工厂的个数接下来 N 行每行包含两个整数 Xi, Pi, Ci, 意义如题中所述
Output
仅包含一个整数, 为可以找到最优方案的费用
- Sample Input
- 3
- 0 5 10
- 5 3 100
- 9 6 10
- Sample Output
- 32
- HINT
在工厂 1 和工厂 3 建立仓库, 建立费用为 10+10=20, 运输费用为(9-5)*3 = 12, 总费用 32 如果仅在工厂 3 建立仓库, 建立费用为 10, 运输费用为(9-0)*5+(9-5)*3=57, 总费用 67, 不如前者优
数据规模
对于 100% 的数据, N 1000000 所有的 Xi, Pi, Ci 均在 32 位带符号整数以内, 保证中间计算结果不超过 64 位带符号整数
f[i]表示在 i 建设仓库的最小花费
f[i]=f[j]+cost(j+1,i)
cost 可以用后缀和搞一下
- f[i] = min(f[i], f[j] + cost[j + 1] - cost[i] - (sump[j + 1] - sump[i]) * sumx[i] + c[i]);#include < iostream > #include < cstring > #include < cstdio > #define N(1000000 + 100)#define LL long long using namespace std;
- LL f[N],
- sump[N],
- sumx[N],
- x[N],
- p[N],
- c[N],
- cost[N],
- n;
- LL q[N],
- head,
- tail;
- LL K(LL j) {
- return - sump[j + 1];
- }
- LL B(LL j) {
- return f[j] + cost[j + 1];
- }
- LL Y(LL i, LL j) {
- return K(j) * sumx[i] + B(j);
- }
- bool cover(LL x1, LL x2, LL x3) {
- LL w1 = (K(x3) - K(x1)) * (B(x1) - B(x2));
- LL w2 = (K(x2) - K(x1)) * (B(x1) - B(x3));
- return w1 >= w2;
- }
- int main() {
- scanf("%lld", &n);
- for (int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &x[i], &p[i], &c[i]);
- for (int i = n; i >= 1; --i) {
- sump[i] = sump[i + 1] + p[i]; //i 到 n 的产品和
- sumx[i] = x[n] - x[i]; //i 到 n 的距离
- }
- for (int i = n - 1; i >= 0; --i) cost[i] = cost[i + 1] + p[i] * sumx[i]; //cost[i]表示 i..n 物品都运到 n 的总花费
- head = 1,
- tail = 1;
- for (int i = 1; i <= n; ++i) {
- while (head < tail && Y(i, q[head]) >= Y(i, q[head + 1])) head++;
- f[i] = Y(i, q[head]) - cost[i] + sump[i] * sumx[i] + c[i];
- while (head < tail && cover(i, q[tail], q[tail - 1])) tail--;
- q[++tail] = i;
- }
- printf("%lld", f[n]);
- }
1096. [ZJOI2007]仓库建设斜率优化 DP
来源: http://www.bubuko.com/infodetail-2544860.html