重庆市城市建设档案馆官方网站携程网网站推广方式

重庆市城市建设档案馆官方网站,携程网网站推广方式,建设外贸网站报价,湖南人文科技学院官网录取查询题目描述 孟加拉板球控制委员会决定在巴里萨尔建造一座新的国际板球场。该体育场形状为凸多边形#xff0c;需要在外部安装泛光灯以便在灯光下比赛。每个泛光灯可以照亮体育场的某些边#xff0c;建造每个灯需要一定成本。 照亮条件 #xff1a;一条边被某个灯照亮#xff…题目描述孟加拉板球控制委员会决定在巴里萨尔建造一座新的国际板球场。该体育场形状为凸多边形需要在外部安装泛光灯以便在灯光下比赛。每个泛光灯可以照亮体育场的某些边建造每个灯需要一定成本。照亮条件一条边被某个灯照亮当且仅当该边的外法向量与从灯到该边某点的光线向量之间的夹角为锐角。输入格式每个测试用例以一个整数NNN开始表示凸多边形的边数3≤N≤303 \le N \le 303≤N≤30。接下来NNN行按逆时针顺序给出多边形顶点的坐标。然后是一个整数MMM1≤M≤10001 \le M \le 10001≤M≤1000表示可选灯的位置数量。接下来MMM行每行包含三个整数x,y,cx, y, cx,y,c表示灯的位置坐标(x,y)(x, y)(x,y)和建造成本ccc。所有灯的位置都在多边形外部。输入以N0N 0N0结束。输出格式对于每个测试用例输出完全照亮所有边的最小成本。如果不可能完全照亮输出Impossible.。题目分析本题要求选择一组灯使得凸多边形的所有边都被至少一盏灯照亮且总成本最小。这是一个几何覆盖问题与组合优化问题的结合。关键难点几何判断如何判断一盏灯能否照亮某条边覆盖性质对于凸多边形一盏灯能照亮的边具有什么特征环形结构多边形是闭合的如何正确处理首尾相连的情况优化选择如何在众多灯中选择最小成本的组合解题思路1. 几何判断条件对于一条边ABABAB从顶点AAA到BBB按逆时针顺序边向量AB⃗B−A\vec{AB} B - AABB−A外法向量将AB⃗\vec{AB}AB顺时针旋转90∘90^\circ90∘得到n⃗(ABy,−ABx)\vec{n} (AB_y, -AB_x)n(ABy​,−ABx​)灯LLL到顶点AAA的向量v⃗L−A\vec{v} L - AvL−A照亮条件n⃗⋅v⃗0\vec{n} \cdot \vec{v} 0n⋅v0即点积为正表示两向量夹角为锐角。注意为什么用顺时针旋转而不是逆时针因为题目中给出的条件是“外法向量”对于逆时针排列的多边形外法向量实际上是顺时针旋转得到的。2. 重要观察连续覆盖性对于凸多边形一盏灯能照亮的边是连续的一段。原因外法向量沿多边形边界连续变化照亮条件点积000是连续的因此如果一盏灯能照亮边iii和边jjjiji jij那么它一定能照亮所有iii到jjj之间的边这个性质将问题转化为区间覆盖问题。3. 区间表示与处理将多边形的NNN条边编号为000到N−1N-1N−1。对于每盏灯找出它能照亮的最长连续边段[L,R][L, R][L,R]。由于多边形是环形的可能出现LRL RLR的情况即跨越N−1N-1N−1到000。处理方法如果L≤RL \le RL≤R区间为[L,R][L, R][L,R]如果LRL RLR将其转换为[L,RN][L, RN][L,RN]其中右端点加NNN使其连续4. 动态规划求解定义dp[i][j]dp[i][j]dp[i][j]表示从顶点iii开始覆盖到顶点jjj包含的所有边的最小成本。这里iii和jjj的取值范围可以扩展到[0,2N−1][0, 2N-1][0,2N−1]以处理环形。状态转移对于每个灯的覆盖区间[l,r][l, r][l,r]及其成本ccc如果已经覆盖到lll即dp[i][l]dp[i][l]dp[i][l]已知那么可以选择这盏灯将覆盖范围扩展到l1,l2,…,rl1, l2, \ldots, rl1,l2,…,r更新dp[i][j]min⁡(dp[i][j],dp[i][l]c)dp[i][j] \min(dp[i][j], dp[i][l] c)dp[i][j]min(dp[i][j],dp[i][l]c)其中j∈[l1,r]j \in [l1, r]j∈[l1,r]初始化dp[i][i]0dp[i][i] 0dp[i][i]0从iii开始覆盖到iii的成本为000表示还没覆盖任何边环形处理由于我们复制了区间将[l,r][l, r][l,r]也复制为[lN,rN][lN, rN][lN,rN]最终答案应从所有dp[i][j]dp[i][j]dp[i][j]中寻找其中j≥iNj \ge i Nj≥iN表示覆盖了至少NNN条连续的边即覆盖了整个多边形。5. 算法步骤总结读取输入多边形顶点和灯的信息生成区间对于每盏灯找出它能照亮的最长连续边段并转换为合适的区间表示动态规划使用上述动态规划方法计算最小成本判断答案如果最小成本为无穷大则输出Impossible.否则输出该成本复杂度分析几何判断O(M×N)O(M \times N)O(M×N)区间生成O(M×N)O(M \times N)O(M×N)动态规划状态数O(N2)O(N^2)O(N2)转移O(M×N)O(M \times N)O(M×N)总复杂度O(M×N2)O(M \times N^2)O(M×N2)由于N≤30N \le 30N≤30M≤1000M \le 1000M≤1000计算量在可接受范围内代码实现// Barisal Stadium// UVa ID: 10641// Verdict: Accepted// Submission Date: 2025-12-21// UVa Run Time: 0.010s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF0x3f3f3f3f,MAXN32,MAXM1024;structPoint{intx,y;Point(){}Point(intx,inty):x(x),y(y){}Pointoperator-(constPointb)const{returnPoint(x-b.x,y-b.y);}intdot(constPointb)const{returnx*b.xy*b.y;}};intn,m;Point poly[MAXN],lights[MAXM];intcosts[MAXM];// 判断灯是否能照亮边ab从顶点a到bboolcanCover(intlightIdx,inta,intb){Point edgepoly[b]-poly[a];// 外法向量顺时针旋转90度Pointnormal(edge.y,-edge.x);// 从灯到顶点a的向量Point veclights[lightIdx]-poly[a];// 法向量与光线向量夹角为锐角 点积 0returnnormal.dot(vec)0;}structInterval{intl,r,cost;booloperator(constIntervalother)const{// 先按起点排序再按终点排序if(l!other.l)returnlother.l;returnrother.r;}};// 直接生成所有可能区间vectorIntervalgetAllIntervals(){vectorIntervalintervals;for(inti0;im;i){// 找到第一个可以覆盖的顶点区间intleft-1,right-1;for(intj0;jn;j){if(canCover(i,j,(j1)%n)){leftj;right(j1)%n;break;}}// 因为是凸多边形一盏灯不可能覆盖所有边所以向左侧和右侧扩展时必定不会相遇// 向左侧扩展while(canCover(i,(left-1n)%n,left))left(left-1n)%n;// 向右侧扩展while(canCover(i,right,(right1)%n))right(right1)%n;// 调整覆盖区间if(leftright)intervals.push_back({left,right,costs[i]});elseintervals.push_back({left,rightn,costs[i]});}// 按照覆盖区间的左端点优先进行排序sort(intervals.begin(),intervals.end());returnintervals;}intsolve(){// 获取所有灯的覆盖区间已排序vectorIntervalintervalsgetAllIntervals();// 状态定义dp[i][j]从顶点i开始覆盖覆盖到顶点j之间的边的最小费用intdp[64][64];memset(dp,0x3f,sizeofdp);for(inti0;in;i)dp[i][i]0;for(autoitl:intervals){intlastitl.l;for(inti0;ilast;i){if(dp[i][last]INF)continue;for(intjitl.l1;jitl.r;j)dp[i][j]min(dp[i][j],dp[i][last]itl.cost);}}// 确定最小费用注意覆盖区间长度必须为nintanswerINF;for(inti0;in;i)for(intjin;j2*n;j)answermin(answer,dp[i][j]);returnanswer;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinnn){for(inti0;in;i)cinpoly[i].xpoly[i].y;cinm;for(inti0;im;i)cinlights[i].xlights[i].ycosts[i];intresultsolve();if(resultINF)coutImpossible.;elsecoutresult;cout\n;}return0;}总结本题的关键在于将几何问题转化为区间覆盖问题并利用动态规划求解。主要技巧包括几何判断简化通过点积判断照亮条件避免复杂的角度计算连续覆盖性质利用凸多边形的特性将灯覆盖范围表示为连续区间环形处理通过复制区间和调整端点将环形问题转化为线性问题动态规划优化使用dp[i][j]dp[i][j]dp[i][j]状态表示覆盖区间的最小成本这个解法充分利用了题目的限制条件N≤30N \le 30N≤30在时间和空间上都是高效的。通过本题我们学习了如何将复杂的几何问题与经典的区间覆盖动态规划相结合这是一个很好的算法设计范例。