照亮体育馆 Barisal Stadium

UVA10641

题目为逆时针顺序编号，这里直接将数组开两倍来处理环。（然而不知为啥开到1000也能过）

定义：

Corners[i]Corners[i]Corners[i]为体育馆点的坐标。

Lights[i]Lights[i]Lights[i]为灯的坐标及费用。

IsShineOnCur[i]IsShineOn_{Cur}[i]IsShineOnCur[i]表示第CurCurCur盏灯是否能照到iii，用于计算范围。

RangeCurRange_{Cur}RangeCur为第CurCurCur盏灯的照射范围，从LeftLeftLeft到RightRightRight，用于初始化dpdpdp

dp[Left][Right]dp[Left][Right]dp[Left][Right]为从第LeftLeftLeft盏灯照到第RightRightRight盏灯的最少花费。

初始化IsShineOnCur[i]\pmb{IsShineOn_{Cur}[i]}IsShineOnCur[i]IsShineOnCur[i]IsShineOnCur[i]：

令A、BA、BA、B两点为体育馆的两点，CCC为体育馆的一盏灯，那么CCC要想照亮边ABABAB，那么必须有0∘<∠BAC<180∘0^{\circ}< ∠BAC< 180^{\circ}0∘<∠BAC<180∘（手动转一转就知道了）

因为有：

sin(∠BAC)=AB⃗×AC⃗sin(∠BAC)=\vec{AB}×\vec{AC}sin(∠BAC)=AB×AC并且当sinθ>0sin\theta>0sinθ>0时，θ∈(0∘,180∘)\theta\in(0^{\circ},180^{\circ})θ∈(0∘,180∘)。

因此只要叉乘大于0即可。注意是逆时针的顺序。

//Cur为灯编号

void InitIsShineOn(const int& Cur) {

	memset(IsShineOn, false, sizeof(IsShineOn));

	for (int i = 1; i <= N; ++i) {

		//i以及i的下一个点位体育馆的点

		int&& Position = i % N + 1;

		//如果叉乘大于0

		IsShineOn[i] =

			(Lights[Cur].x - Corners[i].x) * (Corners[Position].y - Corners[i].y)

			>

			(Corners[Position].x - Corners[i].x) * (Lights[Cur].y - Corners[i].y);

	}

	return;

}

初始化RangeCur\pmb{Range_{Cur}}RangeCurRangeCurRangeCur：

扫一遍即可

void InitRange(const int& Cur) {

	if (IsShineOn[1] && IsShineOn[N]) {

		Range.Left = N;

		Range.Right = 1;

		while (IsShineOn[Range.Left]) {

			--Range.Left;

		}

		while (IsShineOn[Range.Right]) {

			++Range.Right;

		}

		++Range.Left;

		--Range.Right;

		Range.Right += N;

	}

	else {

		Range.Left = 1;

		Range.Right = N;

		while (!IsShineOn[Range.Left]) {

			++Range.Left;

		}

		while (!IsShineOn[Range.Right]) {

			--Range.Right;

		}

	}

	return;

}

dp初始化：

dp=infif(第Cur盏灯能照亮Left到Right)dp[Left][Right]=min(dp[Left][Right],Lights[i].Cost])dp=inf\\if(第Cur盏灯能照亮Left到Right)\\dp[Left][Right]=min(dp[Left][Right],Lights[i].Cost])dp=infif(第Cur盏灯能照亮Left到Right)dp[Left][Right]=min(dp[Left][Right],Lights[i].Cost])

//判断第Cur盏灯能否照亮(Left,Right)的范围

bool Judgt(const int& Left, const int& Right) {

	return

		Range.Left - N <= Left && Range.Right - N >= Right

		||

		Range.Left <= Left && Range.Right >= Right

		||

		Range.Left + N <= Left && Range.Right + N >= Right;

}

void InitDP(const int& Cur) {

	for (int Length = 0; Length < N; ++Length) {

		for (int Left = 1; Left <= 2 * N - 1; ++Left) {

			int&& Right = Left + Length;

			if (Right > 2 * N - 1) {

				break;

			}

			if (Judgt(Left, Right)) {

				dp[Left][Right] = min(dp[Left][Right], Lights[Cur].Cost);

			}

		}

	}

	return;

}

转移方程：

dp[Left][Right]=min(dp[Left][k]+dp[k+1][Right])Left≤k<Rightdp[Left][Right]=min(dp[Left][k]+dp[k+1][Right])\\Left\leq k<Rightdp[Left][Right]=min(dp[Left][k]+dp[k+1][Right])Left≤k<Right经典的区间dpdpdp

最后答案为min(dp[i][i+N−1]),(1≤1≤N)min(dp[i][i+N-1]),(1\leq 1\leq N)min(dp[i][i+N−1]),(1≤1≤N)（双倍数组处理环的答案）

AC代码：

#include<iostream>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

#include<map>

using namespace std;

constexpr static long long inf = 0x3f3f3f3f3f3f3f3f;

struct Corner {

	double x, y;

}Corners[31];

struct Light {

	double x, y;

	long long Cost;

}Lights[1001];

struct {

	int Left, Right;

}Range;

int N, M;

bool IsShineOn[1001]{ false };

long long dp[1001][1001];

bool Input() {

	cin >> N;

	if (!N) {

		return false;

	}

	for (int i = 1; i <= N; ++i) {

		cin >> Corners[i].x >> Corners[i].y;

	}

	cin >> M;

	for (int i = 1; i <= M; ++i) {

		cin >> Lights[i].x >> Lights[i].y >> Lights[i].Cost;

	}

	return true;

}

void InitIsShineOn(const int& Cur) {

	memset(IsShineOn, false, sizeof(IsShineOn));

	for (int i = 1; i <= N; ++i) {

		int&& Position = i % N + 1;

		IsShineOn[i] =

			(Lights[Cur].x - Corners[i].x) * (Corners[Position].y - Corners[i].y)

			>

			(Corners[Position].x - Corners[i].x) * (Lights[Cur].y - Corners[i].y);

	}

	return;

}

void InitRange(const int& Cur) {

	if (IsShineOn[1] && IsShineOn[N]) {

		Range.Left = N;

		Range.Right = 1;

		while (IsShineOn[Range.Left]) {

			--Range.Left;

		}

		while (IsShineOn[Range.Right]) {

			++Range.Right;

		}

		++Range.Left;

		--Range.Right;

		Range.Right += N;

	}

	else {

		Range.Left = 1;

		Range.Right = N;

		while (!IsShineOn[Range.Left]) {

			++Range.Left;

		}

		while (!IsShineOn[Range.Right]) {

			--Range.Right;

		}

	}

	return;

}

bool Judgt(const int& Left, const int& Right) {

	return

		Range.Left - N <= Left && Range.Right - N >= Right

		||

		Range.Left <= Left && Range.Right >= Right

		||

		Range.Left + N <= Left && Range.Right + N >= Right;

}

void InitDP(const int& Cur) {

	for (int Length = 0; Length < N; ++Length) {

		for (int Left = 1; Left <= 2 * N - 1; ++Left) {

			int&& Right = Left + Length;

			if (Right > 2 * N - 1) {

				break;

			}

			if (Judgt(Left, Right)) {

				dp[Left][Right] = min(dp[Left][Right], Lights[Cur].Cost);

			}

		}

	}

	return;

}

void Compute() {

	for (int Length = 0; Length < N; ++Length) {

		for (int Left = 1; Left <= 2 * N - 1; ++Left) {

			int&& Right = Left + Length;

			if (Right > 2 * N - 1) {

				break;

			}

			for (int k = Left; k < Right; ++k) {

				if (dp[Left][k] == inf && dp[k + 1][Right] == inf) {

					continue;

				}

				dp[Left][Right] = min(dp[Left][Right], dp[Left][k] + dp[k + 1][Right]);

			}

		}

	}

}

long long DP() {

	memset(dp, 0x3f, sizeof(dp));

	for (int i = 1; i <= M; ++i) {

		InitIsShineOn(i);

		InitRange(i);

		InitDP(i);

	}

	Compute();

	long long Ans = inf;

	for (int i = 1; i <= N; ++i) {

		Ans = min(Ans, dp[i][i + N - 1]);

	}

	return Ans;

}

int main() {

	while (Input()) {

		long long&& Ans = DP();

		if (Ans == inf) {

			puts("Impossible.");

		}

		else {

			cout << Ans << endl;

		}

	}

	return 0;

}

巴特西

照亮体育馆 Barisal Stadium

最新文章

热门文章