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