照亮体育馆 Barisal Stadium
阅读原文时间:2023年07月08日阅读:2

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}}RangeCur​​RangeCur​​​RangeCur​:

扫一遍即可

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;
}