网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[ZJOI2010]基站选址
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | base.in | 输出文件 | base.out |
问题描述
有N个村庄坐落在一条直线上,第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站,那么就成它被覆盖了。如果第i个村庄没有被覆盖,则需要向他们补偿,费用为Wi。现在的问题是,选择基站的位置,使得总费用最小。
输入数据 (base.in)
输入文件的第一行包含两个整数N,K,含义如上所述。
第二行包含N-1个整数,分别表示D2,D3,…,DN ,这N-1个数是递增的。
第三行包含N个整数,表示C1,C2,…CN。
第四行包含N个整数,表示S1,S2,…,SN。
第五行包含N个整数,表示W1,W2,…,WN。
输出数据 (base.out)
输出文件中仅包含一个整数,表示最小的总费用。
样例输入
3 2
1 2
2 3 2
1 1 0
10 20 30
样例输出
4
数据规模
40%的数据中,N<=500;
100%的数据中,K<=N,K<=100,N<=20,000,Di<=1000000000,Ci<=10000,Si<=1000000000,Wi<=10000。