再水群,再划水,我是猪

因为是枚举的每个分支,就是不可能在一个分支没选完就选第二个分支,然后转移就很合理了.就是两个分支可以看成01背包,然后保留多少个可以看成背包容量..就没了 #include <bits/stdc++.h> using namespace std; const int N=105; struct vv{ int to,val; }; vector<vv>v[N]; int dp[N][N];//以i为根节点 保留j的数量能获得的最大价值. int n,q; void dfs(int u) { for(int i=0;i<v[u].size();i++)//枚举节点 ...

挺简单的一个dp..适合练手 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e8; ll dp[205][105][12][12];//到了第i个第一种分配了l个第一种连续j第二种连续k的方案数 int main() { int n1,n2,k1,k2; cin>>n1>>n2>>k1>>k2; dp[1][1][1][0]=1; dp[1][0][0][1]=1; /* 首先分析状态转移再写for. dp[i][l]...

二进制拆分题...没什么好说的,证明看上篇博客/.. #include <bits/stdc++.h> using namespace std; const int N=1e4+5,M=3e5+4e4; int t[N],c[N],p[N]; int id,n; int T[M],val[M]; int f[1005]; inline void init() { for(int i=1;i<=n;i++) { int vnt=1; while(true) { if(p[i]-vnt<0) { val[id]=c[i]*p[i]; T[id]=t[i]*p[i]; id+...

因为任何数都可以用二进制表示,在你的价值里面..然后最后一堆可以放一起的原因是前面可以表示任何数了,最后一堆无非就是填充最后一个1.举个栗子.假设我有个数10101010,很显然的一个结论10000000>1000000+100000+10000+1000+100+1.然后我主位的那个1肯定是可以分解成这么多个1的,因此一个很显然的结论,因为有这些1,小于主位的位数的任何数都可可以表示的,下面就是证明等于主位的1也是可以表示的.这个证明也挺显然的,因为我们已经把下面那些位数的1都提取出来了,所以我们哪位需要缺少一个1,那就是少用那位的1,比如说10101010,我要缺少10,那么很简单,...

cf的每个dp题,都有它的特点吧,这个dp就很有特点,但是不难,也没什么好说的..代码如下: #include <bits/stdc++.h> using namespace std; const int N=5e3+5; int dp[N],a[N],w[N],e[N]; bool mp[N]; //dp[i]表示1~i这段最大的值,a[]数组就是题目给定的,然后w[i]存每个值最左边的位子,e[i]存每个值右边的位子. int main() { int n; scanf("%d",&n); for(int i=0;i<=5000;i++) w[...

一个模拟题,得在自己清醒的时候打...不然就会乱坟岗..思路很简单,就是找到两个质数是不是差>(k+1),因为我们都足够聪明.那么,你下次肯定会取1(假设我是FFF),而我取k都到不了,那么我必输.其它肯定是我必胜,因为1,2,3你都不能取.所以这题就没了.但是,细节是真的多...具体看代码吧...码风还行.. #include <bits/stdc++.h> using namespace std; const int N=1e7+5; int prime[N],cnt=0; bool st[N]; void init() { for(int i=2;i<=N-5;i...

挺有意思的一个题目,但是因为放在dp专题,所以在想怎么dp...还是不会dp,在网上也没找到dp的题解...至于这题性质,脑袋编译了下,但是没继续深入证明把他们全部变成偶数即是最优解...在这里阐述下证明..首先假设它们的gcd()为1.那么怎么操作才能使得方案数最小呢?先对序列进行分类分奇偶..首先序列全部为偶数,显然与假设不符..skip..我们采用反证法,假设原序列的gcd为1,且不是全部转化成偶数最优.那么就一定是转化成了序列中的数含有某个奇数因子.假设不是一开始就含有这个奇数因子,那么就不可能通过转化得到,这个也是可以证明的.因为a+b/a-b都是不能提取关于a,b的那个奇数因子的....

ll dp[N][N][2];//深度i 总权值为j 是不是存在权值大于d的边..然后随便转移就好了... #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int N=105; ll dp[N][N][2];//深度i 总权值为j 是不是存在权值大于d的边. int main() { ll n,k,d; cin>>n>>k>>d; dp[0][0][0]=1; for(int i=1;i<=n;i++...

题目的意思就是一个序列本来是0,1,2...n-1.然后要你变成p[0],p[1],p[2]...p[n-1],通过交换相邻的两个数每两个相邻的数都可以交换一次,你可以选择交换的顺序.问你有多少种交换顺序?很有意思的一道记忆化搜索题目,emm,大佬教我做的...具体怎么做呢?就是一个典型的分治,加记忆化搜索..分治就是枚举要交换的顺序,具体在哪个点交换,很显然的一个结论,假如那个点交换了,就相当于断开了,然后就可以分治了...具体再记忆化搜索下就可以了~dp[l][r][st][ed].表示区间l-r中开头为st,结尾是ed,然后交换的好序列的方案数是多少.然后复杂度是O(n^5)代码如下: ...

一道cf的dp题,也挺好的,虽然没牛客难..牛客还是牛/..这题是可以选择单词断开然后连起来,类似环.考虑dp,令dp[0][i]为操作i次是原串的方案数,dp[1][i]为操作i次是其他串的方案数.然后显然就有两个dp方程. dp[0][i]=dp[1][i-1]*(n-1). dp[1][i]=dp[0][i-1]+dp[1][i-1]*(n-2).然后比较下两个串,对第二个串看成环进行考虑,假如开始相同就是+dp[0][k],不然就是+dp[1][k]. #include <bits/stdc++.h> using namespace std; const int N=1e3...

是一个组合数学问题,朴素的对于每个都不取k,那就是两个for的事.但是对于取k,我们应该如何分析呢?总的是n,我们拿走k个.在拿走的过程中,我们考虑始终保留两个特殊的,假设说我不存在取的过程,那么这两个产生的贡献必定是一次lcp.但是我们考虑拿走,这个它会多几次呢?其实也挺显然的,C(n-2,k)考虑保留这两个,然后再取走k就没了.那么就变成了如何快速的求两个的lcp,可以直接存下每个的哈希值然后二分..但是呢?这题可以直接暴力比较emm..很水吧,优化数据结构就交给徐鹏大佬了???反正我不是学数据结构的.. #include <bits/stdc++.h> using names...

不努力永远都只能是菜鸡,菜鸡..这题咋一眼看会觉得很难,但是呢.首先的矩阵大小是hw的,但是他只要求nm的任意加起来为奇数.当然题目似乎没讲只能填1~9的数..你会发现假如第一个nm的矩阵确认,那么符合条件的填法也是确认了..因为为了维护奇数,我平移一个数,移进来的数和移出去的数奇偶性一定是一样的,那么问题就变成了,填第一个n*m的矩阵满足各行各列都是奇数的有多少种,当然,后面的也得合法,如此,题目就简单了许多...代码有注释: #include <bits/stdc++.h> using namespace std; #define int long long const int...

期望dp哎,虽然以前也写过,但是不系统..虽然看到还是很迷茫的.题目描述: 有一个游戏平板上面有n×m个格子，一开始每个格子都是关闭的，每个格子里面都有一个标记 已知每种标记恰好出现两次，也就是一共有n*m/2种标记 规定一次移动为依次(one by one不是同时)打开一对格子查看里面的标记，如果标记不一样，格子会自动关闭，但是你的记忆是超强了，看过了就不会忘，如果标记是一样的，格子从此就一直保持打开状态，当所有格子都打开时游戏结束 请算出游戏结束的最少期望步数首先设dp[i][j]表示i个打开了,j个没打开的期望.然后就是转移了. dp是由已知向未知转移的.那么,我们怎么转移呢?众所周知转...