f题 路径可以拆成两条链的合成，我们枚举两条链的交点 siz[i]表示以i为根的子树大小 维护dp[i]表示，当i作为链首时，以i为根往下走一条路时的最大连通块的size 我们设first为i的第1大儿子.second为第二大儿子,third为第三大儿子 如何维护dp[i]? 假设我们现在在第i个结点,我们肯定贪心地去消掉第一大儿子的size，所以我们接下来一步会往第一大儿子走，此时dp[i] = max(dp[first] , siz[second])，要么继承最大儿子的答案，要么取第二大儿子的size dp[i]只是维护好了单链，现在考虑两条链（即路径） 我们考虑i作为两条链的交点，那么我...

题目大意：给定棋盘，棋盘上有若干个被删除的点，现在有1*2多米诺骨牌，求至少多少张将棋盘全覆盖（可越界可重叠）（这题是这题的升级版 思路：二分图匹配 对于多米诺骨牌来说，它有两个点。我们将一张骨牌拆成两个点，再将棋盘黑白染色，不难发现，两个点的颜色一定不同，至此可以建图了，一个棋盘可以这样染色 10101 01010 10101 然后分黑白两个集合，假设我把黑点作为左集合，那么那个黑点周围存在的白点就是黑点要连的边，跑一遍二分图匹配，我们可以求出不重叠的情况下尽量覆盖多的点的最小边数，最后还剩一些孤立的点，需要单独对它覆盖，这些点的数量 = =存在的总点数 - 最大边数*2，所以ans = 存...

单调栈对每个i求它最左和最右可以延伸到哪，然后维护这个延伸区间*i的高度的最大值即是答案 #include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <cstdlib> #include <algorithm> #include <map> #include <vector> #include <queue> #include <set> using namespace ...

如题

#include <bits/stdc++.h> #define IOS std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); using namespace std; typedef long long ll; const int N=10010; int a[N]; struct ty { ll sum,jia,cheng,ping; //和 + * 平方和 }tree[4*N]; void pushup(int p, int l, int r) { tree[p...

//传球游戏 //dp //f[i][j]表示第j次传球传到i的可能数 //f[i][j]=f[i-1][j-1]+f[i+1][j-1] //首尾的人特判 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll f[35][35]; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; f[1][0]=1;//第...

//迷雾森林 //dp优化 //快读+图和dp存一起 //注意取模 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int p=2333; inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; } ll f[30...

//过河卒 //dp #include<bits/stdc++.h> using namespace std; typedef long long ll; ll mp[30][30]; ll f[30][30]; // int dir[][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};//八个方向 int xx[10]; // 存控制点行 int yy[10]; //存控制点列 int main() { ios::sync_with_stdio(false); cin.tie(0);co...

//花店橱柜 //dp #include<bits/stdc++.h> using namespace std; typedef long long ll; ll mp[110][110]; //存输入数据 ll f[110][110]; //f[i][j]表示必选第1 ~ i种花放在前j个花瓶的方法 ll res[110]; // 每种花所在的花瓶 int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); memset(f,-0x3f,sizeof(f));//状态初始化，一开...

//贪心 #include <bits/stdc++.h> #define maxn 0x3f3f3f3f using namespace std; typedef long long ll; priority_queue<int, vector<int >, less<int > > q; //建大根堆 struct jian { ll tt,d;//定义耗时和截止时间 }t[200000]; bool cmp(jian a,jian b) // 假先修截止时间早的 { if(a.d!=b.d) return a...

#include <bits/stdc++.h> using namespace std; typedef long long ll; int deal(int l1,int r1,int l2,int r2,int k)//区间长度2^k { if(l1>r1||l2>r2) return 0; if(l1>l2) {swap(l1,l2);swap(r1,r2);}//把第一个区间放左边 if(r2<=r1) return r2-l2+1;//如果第二个区间包含在第一个区间内 if(l1==l2) r...

//最近对Raid #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <cstring> #define minn -10000 #define maxn 0x3f3f3f3f using namespace std; typedef long long ll; struct node { int x,y; int k;//判断是agent or station }t[1000005]; bool...