Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 单调队列优化DP，时间复杂度O(N)

Posted by yousiki at 2016-08-03 21:27:04 on Problem 2355
```#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

ostream &debug = cout;
typedef long long LL;

/* POJ 2355 */

const int N = 10005;
const int INF = 0x3f3f3f3f;

int n, s, t, dis[N], dp[N], l[3], c[3];
deque<int> q[3];

signed main(void) {

/* prepare */
memset(dis, 0, sizeof(dis));
memset(dp, 0x3f, sizeof(dp));

/* input */
for (int i = 0; i < 3; i++)scanf("%d", l + i);
for (int i = 0; i < 3; i++)scanf("%d", c + i);
scanf("%d%d%d", &n, &s, &t);
for (int i = 2; i <= n; i++)
scanf("%d", dis + i);
if (s > t)swap(s, t);

/* dynamic programming */
dp[s] = 0;
for (int i = 0; i < 3; i++)q[i].push_back(s);
for (int i = s + 1; i <= t; i++) {
for (int j = 0; j < 3; j++) {
while (!q[j].empty() && dis[i] - dis[q[j].front()] > l[j])
q[j].pop_front();
if (!q[j].empty())
dp[i] = min(dp[i], dp[q[j].front()] + c[j]);
}
for (int j = 0; j < 3; j++) {
while (!q[j].empty() && dp[q[j].back()] >= dp[i])
q[j].pop_back();
q[j].push_back(i);
}
}

/* output */
printf("%d\n", dp[t]);

#ifndef ONLINE_JUDGE
system("pause");
#endif // !ONLINE_JUDGE

}```

Followed by: