双端队列
挑战程序竞赛系列（56）：4.4 双端队列（3）
方法1
起初用记忆化搜索来写，可以有如下定义f(i, t)表示当前位置下的最小代价，但同时还有前一轮带来的时间总和。
所以有如下代码：
public int f(int i, int t) {
if (i >= N) return 0;
int cost = 0;
int time = t + S;
int res = INF;
for (int j = i; j < N; ++j) {
cost += jobs[j].c;
time += jobs[j].t;
res = Math.min(res, f(j + 1, time) + cost * time);
}
return res;
}TLE，所以接着采用状态记忆，定义mem[i][t]，呵呵，MLE。
看来只能找一维的dp了，不过此题很巧妙，可以观察下累加的时间代价：
5 5 10 14 14
我们可以看成如下：
0 0 0 4 4
0 0 5 4+5 4+5
5 5 5+5 4+5+5 4+5+5
于是咱可以定义如下dp：
dp[i] 表示从i到N的最小代价
递推式如下：
dp[i] = min{dp[j] + (T[j] - T[i] + S) * (C[N] - C[i])}
j > i && j <= N
T[i]表示时间累加和
C[i]表示代价累加和不过照着它写依旧会超时，在hankcs博文里，指出一个批次最多不会超过200个任务，所以可以限制下搜索分支。
代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P1180.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 10000 + 16;
static final int INF = 0x3f3f3f3f;
int N, S;
int[] dp = new int[MAX_N];
class Job{
int t;
int c;
public Job(int t, int c) {
this.t = t;
this.c = c;
}
}
Job[] jobs;
void solve() {
N = ni();
S = ni();
jobs = new Job[N];
for (int i = 0; i < N; ++i) {
jobs[i] = new Job(ni(), ni());
}
int[] C = new int[N + 1];
for (int i = 0; i < N; ++i) {
C[i + 1] = C[i] + jobs[i].c;
}
Arrays.fill(dp, INF);
dp[N] = 0;
for (int i = N - 1; i >= 0; --i) { // 未知 求已知
int cc = C[N] - C[i];
int tt = S;
for (int j = 1; j + i <= N && j <= 200; ++j) {
tt += jobs[i + j - 1].t;
dp[i] = Math.min(dp[i], tt * cc + dp[j + i]); // 有个技巧 和 求解思路在里头 ，主要观察 tt的 结构易知
}
}
out.println(dp[0]);
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}方法2
嗯，此处是DP优化知识了，具体用到了凸包和斜率优化两个概念，第一次接触就说的详细点，自己也是恶补了一大段时间。
alt text
精髓就在这四句话，简单来说，min是一条条线段集合，而由于它的遍历结构很特殊，min中的线段是一条一条增加的，而每个时刻，我们只需要取最小即可，如果想办法能够把之前的状态记录下来，并维持有序就可以在常数时间内从集合中找出最小代价。
当然还有一点非常重要，虽然x在不断变化，但是x之前的系数，和之后的值只跟j相关，这就可以把它们看成一个个固定的点，而x变大or变小，并不影响最终的取值，既然如此，什么时候取到最小值？
可以想象这些点在空间中的二维分布，而在这些点中取得最小值，一定是已知斜率x，不断从负无穷上移碰到的第一个点，所以这里就有了决策点的冗余，只需要维护一个包络就ok了。
这里点的坐标为：(−aj,dp[j]−S[j]+aj×j)(-a_j, dp[j] - S[j] + a_j \times j)，观察得到−aj-a_j是个单调函数，于是咱们就可以利用双端队列去构造包络，此处是凸包的相关知识（其中的一种构造凸包方法就是利用有序的横坐标or有序的纵坐标）
注意两点：
- 头部元素不是最小删除（可能是因为斜率的单调性）
- 尾部元素不可能成为最小删除（这是因为固定斜率下取最小值，不取凸包内部的点，属于冗余信息）
很多细节问题，上凸下凸，斜率单调递增or单调递减，不动点是否有序，还需勤加练习。
针对此题开始构建：
dp[i] = min{dp[j] + (T[j] - T[i] + S) * (C[N] - C[i])}
移项：
dp[i] = (C[N] - C[i]) * (S - T[i])
+ min{dp[j] + C[N] * T[j] - C[i] * T[j]}
确定不动点：
(-T[j], dp[j] + C[N] * T[j])好了，代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P1180.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 10000 + 16;
static final int INF = 0x3f3f3f3f;
int N, S;
int[] T;
int[] C;
int[] time;
int[] cost;
int[] dp;
int[] deq;
void solve() {
N = ni();
S = ni();
time = new int[N];
cost = new int[N];
for (int i = 0; i < N; ++i) {
time[i] = ni();
cost[i] = ni();
}
T = new int[N + 1];
C = new int[N + 1];
for (int i = 0; i < N; ++i) {
T[i + 1] = T[i] + time[i];
C[i + 1] = C[i] + cost[i];
}
dp = new int[MAX_N];
deq = new int[MAX_N];
Arrays.fill(dp, INF);
int s = 0, t = 1;
dp[N] = 0;
deq[0] = N;
for (int i = N - 1; i >= 0; --i) {
while (t - s > 1 && f(i, deq[s]) >= f(i, deq[s + 1])) s++;
dp[i] = f(i, deq[s]);
while (t - s > 1 && check(deq[t - 2], deq[t - 1], i)) t--;
deq[t++] = i;
}
out.println(dp[0]);
}
public int f(int i, int j) {
return (C[N] - C[i]) * (S - T[i]) + dp[j] + C[N] * T[j] - C[i] * T[j];
}
public boolean check(int f1, int f2, int f3) {
long a1 = -T[f1], b1 = dp[f1] + T[f1] * C[N];
long a2 = -T[f2], b2 = dp[f2] + T[f2] * C[N];
long a3 = -T[f3], b3 = dp[f3] + T[f3] * C[N];
return (a2 - a1) * (b3 - b2) <= (b2 - b1) * (a3 - a2);
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}
alt text
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年09月11日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录