做网站需要架构师吗,网站建设无底薪提成,开发公司成本管理,免费建站的网站参考博客#xff1a;http://www.cnblogs.com/waldenlake/p/9750249.html 题意#xff1a;将一棵n个点的带权有根树剖分成尽量少的链#xff0c;使得 #xff08;1#xff09;链的两个端点是祖先关系 #xff08;2#xff09;链含有的顶点个数小于等于L #xff08;3http://www.cnblogs.com/waldenlake/p/9750249.html 题意将一棵n个点的带权有根树剖分成尽量少的链使得 1链的两个端点是祖先关系 2链含有的顶点个数小于等于L 3链上所有点的点权和小于等于S。求出最少链的数量如果无解输出-1。N105 思路 想法非常的新颖 根据子节点的情况来决定父节点是跟随某个子节点继续向上还是自己独立开始一段新的path。 但是想想这个问题的性质有个疑问局部最优会导致全局最优吗答案是肯定的所以直接上贪心 我们来看这个贪心的性质就是有两个叶子节点a,b他们有公共的父节点c沿着ab一直向上寻找不同问题有不同寻找方向一般从下网上但别被拘束直到长度或者w超限假设a能到c上面的一个节点b却能到c上面的三个节点那么这三个节点划分到b的path为最优因为我总不至于能包含却不去包含他们的。 就是说即便先选了a向上追溯并染色到了c上1点后选了b向上追溯并染色到了c上3点我们不就是等于说a的后半段不跟a了改成属于b的path。因为我们总是改变后半段的归属右总是从叶子节点开始所以这种贪心总是能得到更好的结果而且保证最好的结果是总能出现的。 下面的代码是可以hack的因为没有保证每次都是从叶子节点开始寻找只要做一次bfs对层次作排序就能保证son总是出现father后 \没想到div2最后一题居然这么简单的贪心就可以解决。。还是思维不够#$% #includebits/stdc.h
using namespace std;#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pairint,int
#define all(v) v.begin(),v.end()const int N 1E53;ll w[N],p[N];
int vis[N];int main(){ll n,l,s;cinnls;int f0;for(int i1;in;i){cinw[i];if(w[i]s)f1;}for(int i2;in;i)cinp[i];if(f){printf(-1\n);return 0;}int ans 0 ;//其实还不太准确 要保证从叶子开始for(int in;i1;--i){if(vis[i]0){ans;int j i;ll xl l,xs s;while(xs w[j] xl0 j!0){xs - w[j]; vis[j]1;xl--;j p[j];}}}coutansendl;return 0;
} 转载于:https://www.cnblogs.com/wjhstudy/p/9766794.html
