Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator