3689专题

HDU-3689 Let the light guide us 线段树+DP

题意:输入n,m,然后两个n*m的矩阵,第一个代表在这个位置建塔的成本,第二个代表在相应位置建塔能照的距离,要求每行建一个,并且相邻两行的两个塔要满足照的距离之和大于等于列号差。求最小成本。 分析:每一行中建立一个塔后会在这行照亮一段距离,如果下一行中的一个点能照到这段区间,表示这两个是可以同时建的。也就是下一行中的一个点要在这一行中的对应区间找一个成本最小值,动态规划的状态传递比较好写,只是一