believe_what-CSDN博客

原创 SGU 143.Long Live the Queen（女王万岁）

先确定一个根节点，然后dp[u]表示一定取u的联通块的最大点权和 dp[u]=1+∑dp[v]（v是u的孩子并且dp[v]大于0）代码： #include #include #include #include #include #include using namespace std; const int maxn=210000; int head[maxn]={},next[

2018-01-21 22:25:13 330

原创 P3478 [POI2008]STA-Station（sta树树形dp）

典型的sta树得出状态方程dp[u]为将u设置为根节点的全部度数和相加，方程dp[v]=dp[u]+n-2*num[v]（num[v]指的是以v为根节点的子树的节点数）代码： #include #include #include #include #include #include using namespace std; const int maxn=2000100; ty

2018-01-21 21:43:45 300

原创树的直径（树形dp）

设置状态dp[u][2] dp[u][0]表示距离u的最长距离，dp[u][1]表示距离u的次长距离（与最长距离的节点不在同一颗子树上）然后状态方程为 ans=(ans,dp[u][0]+dp[u][1])ans为树的直径答案 #include #include #include #include #include #include using namespace std; co

2018-01-21 20:39:15 2223

原创 P1156 垃圾陷阱

题目链接：https://www.luogu.org/problemnew/show/P1156 设置状态dp[h]=f，h为高度，f为最大生命值，dp[h]只需要记录所吸收的营养（不考虑消耗）,dp[h]>t则状态有效。状态转移方程：dp[j+a[i].h]=max(dp[j+a[i].h],dp[j]),dp[j]+=a[i].f 代码如下： #include #include #i

2018-01-01 14:08:28 322

原创 P1220 关路灯（区间dp）

这题目想了很有一段时间，最后发现关一个区间的路灯最后的位置要么在最左端要么在最右端，只有两种状态所以建立状态，[i,j]表示这个区间的路灯最小消耗，0代表在最左端，1代表在最右端。这题目还有个坑点不能用while(scanf("%d%d",&n,&s)==2)一直90分最后看别人的把while去了就过了。。。汗颜。。。状态方程式dp[j][i][0]=min(dp[j+1][i][0]+(x[

2018-01-01 12:46:36 259

转载 _int128输出挂

转载：http://wangmingxuan.cn/?post=56 std::ostream& operator<<(std::ostream& os, __int128 t) { if (t==0) return os << "0"; if (t<0) { os<<"-"; t=-t; } int a[50],ai=0;

2017-12-28 22:07:54 803

原创 P1970花匠

题目链接：https://www.luogu.org/problemnew/show/1970 方程状态还算蛮好想的，dp[i][0]表示在i出上升dp[i][1]表示在i处下降直接得到状态转移方程if(a[i]>a[i-1]) dp[i][0]=dp[i-1][1]+1;if(a[i] #include #include #include #include #include #in

2017-12-27 19:32:27 263 1

原创 Fibonacci数列的一些性质

记个笔记。。。避免忘记(推导不是原创但忘记在哪看的了。。。） 1.F(0)+F(1)+...+F(n)=F(n+2)-1 2.F(1)+F(3)+...F(2n-1)=F(2n) 3.F(2)+F(4)+...+F(2n)=F(2n+1)-1 4.[F(0)]^2+[F(1)]^2+…+[F(n)]^2=F(n)·F(n+1) 5.F(0)-F(1)+F(2)-…+(-1)^n·F(n)

2017-12-26 18:23:44 919

原创 codeforces 901B GCD of Polynomials

题目链接：http://codeforces.com/problemset/problem/901/B 多项式为n次，gcd的次数又必须是n从中可以发现gcd每次只能将1阶，所以构造方程f(x)=q(x)*x+r(x)。可以看出这是个递推，直接从后面开始往前面递推，最后的gcd状态b一定为0，所以最后状态表示为gcd(a,0)，又因为方程系数的绝对值小于等于1所以a为1，于是列出末状态dp[1]

2017-12-26 18:06:05 326

原创 poj3281最大流（模板）

#include #include #include #include #include #include using namespace std; const int maxn=400+5; const int inf=9999999; struct edge{int to,cap,rev;}; vectorg[maxn]; int level[maxn]={},iter[maxn]

2017-12-22 20:34:29 154

原创 codeforces 903B(暴力)

这道题目简单但是很容易错。。。B题的通过人数少于C题。。。这道题目不管方案数又不限制血药的量所以先喝血药喝到打完怪也死不了的时候即可 #include #include #include #include #include #include using namespace std; int h1,a1,c1,h2,a2; int main() { while(scanf(

2017-12-21 19:36:34 330

原创 codeforces 900D(组合数学+剪枝)

题目链接：http://codeforces.com/problemset/problem/900/D 数列的最大公因数为x则所有的ai均可以由x表示于是若有这样的数组则y%x==0。数组可以分成多个x，于是可以把此题转化成将y/x个x放进m个箱子里（不允许有空箱子），于是这道题便转化成了经典的组合数学问题方案数为C(y/x-1,m-1)把m从2一直叠加到y/x-1于是总共的方案数变化成了2^(

2017-12-21 18:28:19 596

原创 codeforces 893E(组合数学&组合数取mod)

题目链接：http://codeforces.com/problemset/problem/893/ 先质因子分解此题可以转化为n个数字放入y个空格中所以用插空法C(y-1+t,y-1)计算出情况在这里数字还可以是负数所以在原来的基础上将偶数个数字变成负数C(y,0)+C(y,2)+C(y,4)+... 化简为2^(y-1) 推倒： (1+x)^n=C(n,0)+C(n,1)*x+..

2017-12-21 11:12:22 352

原创 codeforces 900C(暴力)

遍历的时候只需要保存最大值和次大值即可若为record则标记为1当删除record数字的时候则要让record个数先减1。因为只能去除一个数字所以保存[0,i]只有一个数字a比当前大的数字b（vector）。这样遍历全部的b就可以判断除掉b可以增加多少record 注意：若为递增数组则需要特判。 #include #include #include #include #include

2017-12-21 10:33:43 313

原创 P2679子串（dp）

题目链接：https://www.luogu.org/problemnew/show/2679 这题目有四个状态dp[2][i][j][k]首先第一个状态1表示选取a[i]，0表示不考虑选不选然后i表示已扫过a字符串的前i个元素j表示构造了前j个b子串k表示有k组子串构造而成于是状态转移方程为：dp[1][i][j][k]=(dp[1][i-1][j-1][k]+dp[0][i-1][j-1][

2017-12-20 23:02:25 247

原创 P1387 dp入门

原题链接：https://www.luogu.org/problemnew/show/P1387 用两个数组进行预处理le[i][j]表示从i,j向左延伸最大的边长up[i][j]表示向上延伸的最大边长然后枚举每一个点再枚举(i,j)到(i-temp,j)temp为当前枚举到的最短边长。复杂度为O(n^3) #include #include #include #include #in

2017-12-19 20:24:25 138

原创 P1719最大加权矩阵

题目链接：https://www.luogu.org/problemnew/show/P1719 这道题目关键在于将维度的技巧。若最大子矩阵从(i,j)到(i1,j1)，可以将他们的同列加起来变成一维{(a(i,j)+a(i,j+1)+...+a(i,j1)),...,a(i1,j)+...a(i1,j1)}。然后再求最大子段问题（dp[i]=max(dp[i-1]+sum[i],sum[i]）

2017-12-19 19:42:56 412

qq_37919863的博客