https://ac.nowcoder.com/acm/problem/15832数据范围不超过10，每种原子的有与无很容易用二进制表示，故明显是状压dp 状态表示dp[i]：当前所有原子的状态为i的所有方案的最大能量值状态计算dp[i] = max(dp[j] + w[p][q])(当前最后一个消失的原子为q，最后一次发生的反应为p碰撞q，易知i状态时p必须q不能存在，p必须存在，j状态时p，q均必须存在) 对于任意状态i的最优解满足最优子结构的证明:(一般都是反证法):我们假设的最优解为dp[i]， 且dp[i] = max(dp[j] + w[p][q])如果dp[i] 不来自某一个dp...

https://ac.nowcoder.com/acm/problem/15034个人体会:题目卡错，多写半年(忘记取模和多组数据QAQ)思路:通过题目的描述，又是给棋盘数据范围又20不到，肯定是状压dp状态表示:dp[i][j]:前i行中，且第i行的放置状态为j的所有方法的cnt状态计算:dp[i][j] += dp[i - 1][k](前提相邻行的士兵不能相邻，即j & k == 0)状态dp的一般流程:设置好状态表示和计算后，先预处理出的合法状态，本题中对于任意一行，其合法条件为1.棋盘为0的位置不放置士兵，即(g[i] & j == g[i]2.同一排士兵不能相邻 即(...

https://codeforces.com/contest/1520###A题目大意:给定一字符串，相同的字符连续的出现一次才算合法，判断字符串是否合法思路:理解了题意直接签到AC代码 #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false); cin.tie(0) #define ll long long #define ull unsigned long long #define SZ(x) ((int)(x).size()) #define all(x)...

题目大意 对于任意一条边，其都只有两种被覆盖的可能:1.被上面的节点(父节点)覆盖2.被下面的节点(子节点)覆盖故容易推出状态表示和方程dp[i][j]:以i为根的子树的所有边被覆盖且i的状态为j的所有方案的数量最小值(j = 0表示i不放士兵，j = 0为i放士兵)转移方程dp[i][0] = ∑(dp[son][1])dp[i][1] = ∑(min(dp[son][1],dp[son][0]) + 1;边界设置:对于叶子节点 dp[i][0] = 0, dp[i][1] = 1; 从定义出发AC代码 #include <iostream> #include <algor...

树的最小支配集问题 题目大意：思路:对于任意一个点，只有三种被覆盖的情况1.被自己覆盖2.被自己的子节点覆盖3.被自己的父节点覆盖故很容易推出状态表示dp[i][j]:以i为根的子树的全部节点被覆盖且i节点的覆盖状态为j的所有方案的节点最小值(其中j = 0表示被自己覆盖，j = 1表示被儿子覆盖， j = 2表示被父亲覆盖)转移方程1.i被自己覆盖：此时与i直接相连的子树可以来自三种状态的任意一种，取最优的一种即可dp[i][0] = ∑(min(dp[son, 0], dp[son, 1], dp[son, 2])) + 12.i被父亲覆盖(容易遗漏的情况)此时与i直接相连的子树的状态不可...

简化版的书上背包 思路:对于以任意节点为根的子树，可以将子树按与根相连的边分组，不同组内所有的子树的可能即为有特定价值与体积的物品。要求以1为根的所有子树中含有j条枝的最大权值树，问题可以转化为从按1为根分组的所有子树中选放入体积为j的背包的所有选法的maxn，然后即可以用分组背包的思路求解,每组中可不选，选第一个，选第二个，balabalabala...【注】:分组背包问题循环遵循:(一般便于空间降维处理)for(分组)for(体积)for(决策) AC代码 #include <bits/stdc++.h> using namespace std; #define IO std:...

吉吉王国 https://ac.nowcoder.com/acm/problem/210473本题是Rinne Loves Edge(https://ac.nowcoder.com/acm/problem/22598)的变体,都是处理剪去树的所有叶子的问题。思路:首先联想到和Rinne Loves Edge相同的做法，即假设总花费最少时，最长长度也最小，但很容易举出反例，例如如下hack数据5 41 2 22 3 12 4 12 5 1故需要找出本题其他的性质，观察到题面还有最长最小，首先考虑二分，如果我们二分枚举允许的最长len，则len越大，可供的选择越多，故允许的len范围大所递推得到的...

题目链接: https://ac.nowcoder.com/acm/contest/11170/B思维题:观察可知c数组只需计算前3项，c[3]~c[n - 1]均为0,故只需分析前三项的情况即可c0 = (sa[n - 1] - sa[0]) * (sb[n - 1] - sb[0]);c1 = (a[0] * b[0]) + a[0] * (sb[n - 1] - sb[1]) + b[0] * (sa[n - 1] - sa[1]);c2 = (a[0] * b[1]) + (a[1] * b[0]);[注]:sa,sb为a,b数组前缀和 代码细节：减法取模操作 -- 化正取模(arr[...

题目链接:https://ac.nowcoder.com/acm/contest/11170/A思维题:观察可知通过题目给定操作至多只能减少一个极长1串，当且仅当输入的01串中出现连续0串或连续1串的长度为1，故可以遍历一遍01串判断是否存在长度为1的连续0或连续1串，同时统计01串中所有连续1串的数量即可。特判:若是在串的首尾出现的长度为1连续0串不能减少极长1串数量 AC代码 #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false); cin.tie(0) ...