HDU 6076 (动态规划)

HDU 6076 Security Check

Problem :

有两个长度为n的队列过安检，每个人有一个特征值。如果两个队列中的第一个人的特征值之差小于等于k，那么一次只能检查其中一个人，否则一次可以检查两个人。每次检查花费1的世时间。问最后检查完所有人之后所需要的时间。(n <= 60000, k <= 10)(3s时限)

Solution :

容易想到一个dp方程，dp[i][j]表示当前检查到a队列第i个人，b队列第j个人。

dp[i][j] = dp[i - 1][j - 1] + 1 ( abs(a[i] - b[j] > k)

dp[i][j] = min(dp[i - 1][j] + dp[i][j - 1]) + 1 ( abs(a[i] - b[j] <= k)

从二维平面的角度考虑，每个点的决策相当于是从左、下、左下三个方向转移过来。

注意到 k<=10，即在多数情况下状态由左下方转移过来，少数点来自于左或下。

因此可以对于每个对角线维护一个dp值，对于每个需要从左或下转移的关键点进行处理。其状态可以由下方或者左方对应的对角线上的状态转移过来。

最后若终点不是关键点，特殊处理一下。

#include <iostream>

#include <algorithm>

using namespace std;

const int INF = 1e8 + 7;

const int N = 600008;

int dp[N << 1], f[N << 1];

int a[N], b[N], ref[N];

int sol[N];

int n, k;

void init()

{

	cin >> n >> k;

	for (int i = 1; i <= n; ++i) cin >> a[i];

	for (int j = 1; j <= n; ++j)

	{

		cin >> b[j];

		ref[b[j]] = j;

	}

}

void solve()

{

	for (int i = - n - 1; i <= n + 1; ++i) dp[i + N] = INF;

	for (int i = 0; i <= n; ++i)

		dp[i + N] = i, f[i + N] = 0;

	for (int i = 0; i <= n; ++i)

		dp[-i + N] = i, f[-i + N] = i;

	for (int i = 1; i <= n; ++i)

	{

		int tot = 0;

		for (int j = a[i] - k; j <= a[i] + k; ++j)

		{

			if (j <= 0) continue;

			if (j > n) continue;

			sol[++tot] = ref[j];

		}

		sort(sol + 1, sol + tot + 1);

		for (int j = 1; j <= tot; ++j)

		{

			int tmp = sol[j] - i + N;

			dp[tmp] = min(dp[tmp + 1] + i - 1 - f[tmp + 1] + 1, dp[tmp - 1] + i - f[tmp - 1] + 1);

			f[tmp] = i;

		}

	}

	if (abs(a[n] - b[n]) > k) dp[N] = dp[N] + n - f[N];

	cout << dp[N] << endl;

}

int main()

{

	cin.sync_with_stdio(0);

	int T; cin >> T;

	while (T--)

	{

		init();

		solve();

	}

}

巴特西

HDU 6076 (动态规划)

HDU 6076 Security Check

最新文章

热门文章