| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
单调队列优化DP,时间复杂度O(N)#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator