wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共6篇）

【每日一题】德玛西亚万岁

solution 状压dp。用数字来表示一行方案，对于一个状态x，如果x的第i位（二进制下）为1，表示这一行的第i个位置安排士兵。否则表示不安排士兵。先把每一行可能的状态都搜出来，也就是在满足相邻两个二进制位不都为1的条件下，搜出所有的方案。可以发现一行的方案数最多不超过400。然后将两个可以...

状态压缩

2020-06-02

2 895

【每日一题】比赛

solution 先考虑对于如何求出解出第道题的概率。直接求并不好求，但是解不出第道题的概率很好求，就是。那么解出第到题的概率就是。因为题目数量非常小。所以可以枚举每道题是否解出来了，然后统计一下每种情况的概率，记录到答案里面即可。 code /* * @Author: wxyww * @Date...

状态压缩概率

2020-05-18

1 662

hdu4899 Hero meet devil

题目链接题意给出一个长度字符串\(T\)，其中只包含四种字符\((A,C,G,T)\),需要找一个字符串\(S\)，使得\(S\)的长度为\(m\)，问\(S\)和\(T\)的\(lcs\)为\(0,1,2...|T|\)时，分别有多少种情况。 \(|T| <= 15,m <= ...

动态规划dp 状态压缩 dp套dp

2019-01-24

0 596

bzoj3900 交换茸角

题目链接思路看到n比较小，可以状压。可以先考虑什么情况下会无法平衡。显然就是排完序之后两两相邻的不能满足小于等于c的限制。状态。用f[i]来表示i集合中的鹿完成交换所需要的次数。预处理。无法平衡的肯定就是INF。已经平衡的是0。其他的先暂设为k-1(k是i集合中鹿的个数)。然后转移。...

动态规划dp 状态压缩

2019-01-24

0 491

bzoj3900 交换茸角

题目链接思路看到n比较小，可以状压。可以先考虑什么情况下会无法平衡。显然就是排完序之后两两相邻的不能满足小于等于c的限制。状态。用f[i]来表示i集合中的鹿完成交换所需要的次数。预处理。无法平衡的肯定就是INF。已经平衡的是0。其他的先暂设为k-1(k是i集合中鹿的个数)。然后转移。...

动态规划dp 状态压缩

2019-01-24

0 472

hdu4899 Hero meet devil

题目链接题意给出一个长度字符串\(T\)，其中只包含四种字符\((A,C,G,T)\),需要找一个字符串\(S\)，使得\(S\)的长度为\(m\)，问\(S\)和\(T\)的\(lcs\)为\(0,1,2...|T|\)时，分别有多少种情况。 \(|T| <= 15,m <= ...

动态规划dp 状态压缩 dp套dp

2019-01-24

0 574