哎呀好几天没写POI题解了 (＞﹏＜)
看着摇曳不定的小旗子深深惶恐
打算开始肝洛谷试炼场的提高分区了【对我就是这么菜…
- 搜索Ex
比暴搜不错得多的题
拆成两问来看 第一问只要从湖边的城市（简称湖城）开始搜索就可以了
第二问的faulse项
用dfs剩的vis统计一下沙漠边缘有哪些点（简称沙城）没被搜到的
true项 蒟蒻一开始想状压
当然 n <= 500 【黑线
后来画了个等高线地形图【划掉
发现如果每个沙城都能有水喝【即true项
每个湖城管辖的沙城都是连续的区间
现在问题就变成了 至少用多少个区间覆盖整个区间
当然这问题长得很DP 但有个贪心更优
借用一位神犇的例子
m为10
N = 7：[1,5]、[1,6]、[3,6]、[1,7]、[6,9]、[9,10]、[7,9]。
先把每个区间（都是闭区间）排序 左区间小的优先
[1,5]、[1,6]、[1,7]、[3,6]、[6,9]、[7,9]、[9,10]
我们从1开始
选择每个区间的代价都是1 选择右区间大的显然更优
所以取[1, 7]
现在左区间小区等于7的区间 在小于等于7的部分已经被覆盖 所以无效了
为使区间连续 我们找（左区间小于等于8的区间）中（右区间最大的区间）
okk
最后附一句 如果找到一个地方 （可用最大右区间）小于（上一个取的区间的左区间）
inline void dfs(int x, int y){
node[x][y].vis = ;
if(x < || x > n || y < || y > m) return ;
for(int i = ; i <= ; i++){
int sx = x + move[i][], sy = y + move[i][];
if(node[sx][sy].w < node[x][y].w){
if(!node[sx][sy].vis){
dfs(sx, sy);
}
node[x][y].l = min(node[sx][sy].l, node[x][y].l);
node[x][y].r = max(node[sx][sy].r, node[x][y].r);
}
}
}
dfs部分
for(int i = ; i <= m; i++)
a[i] = (A){node[][i].l, node[][i].r};
sort(a + , a + m + , cmp);
int i = , j = , ans = ;
while(j <= m){
int k = j;
while(a[i].l <= k){
j = max(j, a[i].r);
i++;
}
j++;
ans++;
}
printf("1\n%d", ans);
贪心部分
吐槽玄学数据…
明明能一次A的wwww【委屈
void dfs(int cur, int from, int to, bool flag){
//cur表示当前要移动的圆盘大小 from表示它在的位置 to表示它要移动到的地方
//flag = 1 表示cur是在进行主操作的点 flag = 0表示cur是为了移动另一个圆盘而移动的
if(from == to){
if(cur > ) dfs(cur - , s[cur - ], flag ? t[cur - ] : to, flag);
/*
当要移动的盘已经在它的目标位置上
如果flag = 1 那么它的主操作已经被完成 需要将主操作传递到下一个级别的圆盘上
flag = 0 那么要把下一个级别的圆盘从它的位置上移动到无关的杆子上
*/
return ;
}
if(cur > ) dfs(cur - , s[cur - ], - from - to, );
//把比它小的所有盘都移到无关的杆子上
printf("move %d from %c to %c\n", cur, turn(from), turn(to));
s[cur] = to; ans++;
//移动后 当前盘已经在目标位置上 与from == to的操作一致
if(cur > ) dfs(cur - , s[cur - ], flag ? t[cur - ] : to, flag);
}
/*
汉诺塔的框架：
将主操作从大盘向小盘传递
移动一个盘的最优策略是把它上面的盘都移到无关杆上
注意的点：
flag的传递
起点终点的选择
输出格式
结束条件(cur == 1)
*/
啊啊啊QAQ 都是泪
有个剪枝不错
if ( sum == || sum + i == target ) //
break;