上海浦东设计网站建设,遵义网站建设中心,无锡 网站开发,软件开发 网站开发公司I. Path Planning
嗯#xff0c;怎么说呢#xff0c;一般二维图#xff0c;数据不是很大的比如n*m*log级别允许的#xff0c;如果一眼不是bfs#xff0c;可以考虑结合一下二分
本题可知#xff0c;只能向下或者向右#xff0c;那么我们就像如果答案为x#xff0c;那么…I. Path Planning
嗯怎么说呢一般二维图数据不是很大的比如n*m*log级别允许的如果一眼不是bfs可以考虑结合一下二分
本题可知只能向下或者向右那么我们就像如果答案为x那么一定会有一条0到x-1的路存在
我们再想一条路肯定是先右再下然后重复进行的类似于一个楼梯的样子。
二分我们知道了但是check里面如何判断才能配合二分呢对于我们check的mid 我们可以先按行排序再按列排序然后按这个先行后列的顺序按我们的原图找0~mid-1的数然后只看列是否满足即可也就是上一个的列值小于等与目前的列值。
int n, m;
int a[N];
bool check(int mid)
{int last -1;for (int i 1; i n; i){for (int j 1; j m; j){if (a[(i - 1) * m j] mid - 1){if (j last)return false;last j;}}}return 1;
}
void solve()
{cin n m;for (int i 1; i n; i){for (int j 1; j m; j){cin a[(i - 1) * m j];}}int l 0, r n * m;while (l r){int mid l r 1 1;if (check(mid))l mid;elser mid - 1;}cout r endl;
}
B. Base Station Construction
题意就是跟你一堆区间每个区间里面必选选一个点问最小花费。
我们考虑从dp下手定义 为代表前 i 个位置且第 i 个位置必选选的最小花费
定义完成以后我们考虑如何转移显然我们要选的哪个点 J 要满足 在 之间不包含完整的一个区间不然就漏掉了转移方程那就是 我们知道了 j 的区间范围但是不能 n方的去转移我们考虑用单调对列来维护 一下 ,那么问题就解决了最后我们在n1位置建一个单点区间以便于我们不用循环最后一个区间来找最小值了。
struct node
{int l, r;bool operator(const node w) const{if (r ! w.r)return r w.r;return l w.l;}
} p[N];
int a[N], b[N], que[N];
void solve()
{int n, m;cin n;vectorint f(n 10); // f[i]表示前i个位置且第i个位置必选的最小花费for (int i 1; i n; i)cin a[i];a[n] 0;cin m;for (int i 1; i m; i){int l, r;cin l r;p[i] {l, r};}sort(p 1, p 1 m);priority_queuePII q;for (int i 1, j 0, k 0; i n; i){while (j m p[j].r i)q.push({p[j].l, p[j].r}), j;if (q.size() q.top().xx k)k q.top().xx;b[i] k;}int hh 0, tt 0; // 一开始里面有个0相当于第一个限制区间前面没有限制区间也就是可以选单点提前push一个0for (int i 1; i n; i){int k b[i];while (hh tt que[hh] k)hh;f[i] f[que[hh]] a[i];cout f[i] endl;while (hh tt f[que[tt]] f[i])tt--;que[tt] i;}cout f[n] endl;
}
