url: https://www.luogu.com.cn/problem/P4310

tag:
动态规划，位运算

思路：
如果用求最长上升子序列的方式来求会超时。这时我们可以观察到因为要满足b_i & b_{i - 1} != 0，所以对于以a_i 结尾的数来说，只要是某一个序列末尾的数的某一位和a_i 都是1就可以想接。所以可以用一个数列bit来存某一位为1时的最长序列。之后更新时只需要枚举a_i 的每一位为1的情况，更新f就行。最后求出最大值后，用这个最大值再来更新当前情况下的bit数组值。对于枚举每一位可以通过lowbit函数求出最低位的1（2^k 的形式），之后再通过map log_2来映射每一个2^k 的 k值即为位数。

代码：

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
int ans;
int f[N];
int bit[N];
map<int, int> log_2;
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    cin >> n;
    for (int i = 0, j = 1; i <= 31; i ++, j <<= 1)
    {
        log_2[j] = i;
    }
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++)
    {
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            f[i] = max(f[i], bit[log_2[low]] + 1);
        }
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            bit[log_2[low]] = max(bit[log_2[low]], f[i]);
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2015

tag：
树形DP，动态规划

思路：
用数组f[u, j] 表示以u为根节点使用不超过 j 条边时最大的苹果数量。和背包问题有点不同的是，对于每一个点来说，假如需要用到某一个子节点来更新，则需要与之想连，所以其实是需要预备那个子节点所连的所有边 + 1的边来更新。所以状态转移方程为 f[u, j] = max(f[u, j], f[u, j - k - 1] + f[v,k] + w).在用二维循环更新时，不能让可能用到的边超过子树拥有的边，所以每次dfs之后还需要用s数组来更新以当前节点为根时所拥有的最大的边数。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 200;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int n, q;
int s[N];
int f[N][N];
void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}
void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j] + 1;
        for (int l = min(s[u], q); l; l --)
            for (int k = min(s[j], l - 1); k >= 0; k --)
                f[u][l] = max(f[u][l], f[u][l - k - 1] + f[j][k] + w[i]);
    }
}
int main()
{
    cin >> n >> q;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c),add(b, a, c);
    }
    dfs(1, 0);
    cout << f[1][q] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P3478

tag:
树形DP，POI，2008

思路：
利用两次dfs，第一次求出以1为根节点时深度和，以及各个节点为根时的子树大小，之后利用第二次dfs求出每个节点为根时的深度和。这个方法称为二次扫描。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int n;
long long res, id;
long long d[N], s[N], f[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u, int fa)
{
    s[u] = 1; d[u] = d[fa] + 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j];
    }
}

void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        f[j] = f[u] + n - 2 * s[j];
        dfs2(j, u);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i ++) f[1] += d[i];
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++) if (f[i] > res) res = f[i], id = i;
    cout << id << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P3047

tag:
树形DP, USACO, 2012

思路：
用f[u,m] 表示以u为根节点，向下走出不超过m步时的权值，d[u, m] 表示以u为根节点，向上或向下走不超过m步时的权值。利用两次dfs分别求出f和d，最后输出每个节点作为根节点时的权值和即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int w[N];
int n, k;
LL f[N][25], d[N][25];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs(int u, int fa)
{
    for (int i = 0; i <= k; i ++) f[u][i] = w[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa)
        {
            dfs(j, u);
            for (int p = 1; p <= k; p ++)
            {
                f[u][p] += f[j][p - 1];
            }
        }
    }
}
void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        d[j][1] += d[u][0];
        for (int p = 2; p <= k; p ++)
        {
            d[j][p] += d[u][p - 1] - f[j][p - 2];
        }
        dfs2(j, u);
    }
}
int main()
{
    cin >> n >> k;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i ++) cin >> w[i];
    dfs(1, 0);
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= k; j ++)
            d[i][j] = f[i][j];
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++) cout << d[i][k] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1944

思路：
用动态规划的思路来做。用f[i]表示以s[i]结尾的括号匹配字符串，属性是最大值。从第二个字符开始检查，如果当前字符为 ）或 ] ，以及距离上一个匹配好的字符串前的一个字符与其相匹配，则更新长度为f[i] = f[i - 1] + 2，同时可以检查前两个字符，如果为 ）或者 ] 说明以那个字符结尾的字符串可以与当前的字符串相连。因为如果可以匹配为字符串则会将结果存在f[i] 中，所以实际上不需要匹配，只需要加上 f[i - f[i - 1] - 2] 即可。最后每次更新下最长的字符串长度和下标，因为要输出第一个最长的，所以只有在严格大于时才更新，最后根据长度和下标从原字符串中构造出答案输出即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int f[N];
char str[N];
int main()
{

    scanf("%s", str + 1);
    cout << str;
    int len = strlen(str + 1);
    int mlen = 0, id = 0;
    for (int i = 2; i <= len; i ++)
    {
        if (str[i - f[i - 1] -1] == '(' && str[i] == ')' || str[i - f[i - 1] - 1] == '[' && str[i] == ']')
        {

            f[i] = f[i - 1] + f[i - f[i - 1] - 2] + 2;
            if (f[i] > mlen)
            {
                mlen = f[i];
                id = i;
            }
        }
    }
    for (int i = id - mlen + 1; i <= id;  i++)
    {
        cout << str[i];
    }
    return 0;
}