【Link】:

【Description】

输入一个凸n（3≤n≤30）边形体育馆和多边形外的m（1≤m≤1000）个点光源，每个点光 源都有一个费用值。选择一组点光源，照亮整个多边形，使得费用值总和尽量小。如图9-31 所示，多边形ABCDEF可以被两组光源{1,2,3}和{4,5,6}照亮。光源的费用决定了哪组解更 优。

【Solution】

首先,处理出每个灯能够照到体育馆的哪些区域;

肯定是一个连续的区域

办法是,以起点和下一个点组成一个向量a1,以起点和要判断的灯组成一个向量a2,看看a2是不是在a1外面;只要两个向量做一下叉积就可以了;

如果小于0,就在外面;

之后,就开始进行DP了;

因为是环形的,可以参考环形石子归并那题;

需要以每个点都作为起点,进行一次dp;

然后获取从这个点i开始,到点i+n之间的最小花费;

(如果大于n表示到下一圈了);

f[j]表示从i..j这一段,最小花费是f[j];

每次,根据已有的f值(一开始是f[i]=0);

然后根据每个灯的范围,看看能不能扩大这个j,即让j往后靠一点,假设到了tj;

然后尝试更新f[tj];

最后在所有的f[i+n]里面,取最小值;

【NumberOf WA】

1

【Reviw】

环形的,一般要枚举每个为起点;

然后做它到环形一周回来的最小价值;

每个灯,能让照射的范围增大,慢慢触及整个区间;

【Code】

#include 
     
      using namespace std;const int N  = 30;const int M = 1e3;const int INF = 0x3f3f3f3f;struct point{    int x,y;};struct node{    int l,r,c;};int n,m,f[2*N+10];point p[N+5];node a[M+10];bool flag[N+10];bool pd(point c,point a,point b){    int x1,y1,x2,y2,x3,y3;    x1 = a.x,y1 = a.y,x2 = b.x,y2 = b.y,x3 = c.x,y3 = c.y;    return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) < 0;}node get_fanwei(point t,int c){    memset(flag,0,sizeof flag);    for (int i = 1;i <= n;i++)        if (pd(t,p[i],p[i+1]))            flag[i] = 1;    if (flag[n] && flag[1]){ // --xxxx--        int l = n,r = 1;        while (l-1 >= 1 && flag[l-1]) l--;        while (r+1 <= n && flag[r+1]) r++;        r+=n;//不可能全照到        return node{l,r,c};    }    //xxx-----xxx    int l = 1,r = n;    while (!flag[l]) l++;    while (!flag[r]) r--;    return node{l,r,c};}bool get_ans(){    int ans = INF;    for (int i = 1;i <= n;i++){        memset(f,INF,sizeof f);        f[i] = 0;        for (int j = 1;j <= n;j++){            int now = i + j - 1;            for (int k = 1;k <= m;k++){                if (a[k].l > now) continue;                int nex = min(i + n , a[k].r + 1);                f[nex] = min(f[nex],f[now] + a[k].c);            }        }        ans = min(ans,f[i+n]);    }    if (ans >= INF) return 0;    return printf("%d\n",ans),1;}int main(){    while (~scanf("%d",&n)){        if (n==0) break;        for (int i = 1;i <= n;i++)            scanf("%d%d",&p[i].x,&p[i].y);        p[n+1] = p[1];        scanf("%d",&m);        for (int i = 1;i <= m;i++){            int x,y,c;            scanf("%d%d%d",&x,&y,&c);            a[i] = get_fanwei(point{x,y},c);        }        if (!get_ans()) puts("Impossible.");    }    return 0;}