10 条题解

  • 1
    @ 2023-2-16 21:35:44

    道路

    #include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int l[41234], r[41234];
int a[41234], b[41234], c[41234];
int f[41234][55][55];
//走到 u 节点，之前有 x 条“左边”未被翻修，y 条“右边”未被翻修
//返回这种状态下，“u 下面的所有子节点的不便利值之和” 的最小值
int dfs(int u, int x, int y)
{
    if (u >= n)
        return c[u] * (a[u] + x) * (b[u] + y);
    if (f[u][x][y] != 0)
        return f[u][x][y];
    //考虑 u 的两条子边，翻修哪条，不翻修哪条。
    f[u][x][y] = min(dfs(l[u], x, y) + dfs(r[u], x, y + 1),
                     dfs(r[u], x, y) + dfs(l[u], x + 1, y));
    return f[u][x][y];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> l[i] >> r[i];
        if (l[i] <= 0)
            l[i] = n - 1 - l[i];
        if (r[i] <= 0)
            r[i] = n - 1 - r[i];
    }
    for (int i = 1; i <= n; i++)
        cin >> a[n - 1 + i] >> b[n - 1 + i] >> c[n - 1 + i];
    cout << dfs(1, 0, 0) << endl;
    return 0;
}
    • 1
      @ 2023-2-14 20:09:59

      P2014 [CTSC1997] 选课

      #include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const int MAXM = 300;
int n, m, root;
int s[MAXN + 5];
int siz[MAXN + 5];
vector<int> e[MAXN + 5];
int dp[MAXN + 5][MAXM + 5]; //dp[i][j] i为根的子树，选择j门课的最大学分
void dfs(int u)
{
    dp[u][1] = s[u];
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        dfs(v);
        for (int j = min(siz[u], m + 1); j > 0; j--)
            for (int k = 1; k <= siz[v] && j + k <= m + 1; k++)
                dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]);
        siz[u] += siz[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int fa;
        cin >> fa >> s[i];
        e[fa].push_back(i);
    }
    dfs(0);
    cout << dp[0][m + 1] << endl;
    return 0;
}
      • 1
        @ 2023-2-10 17:59:16

        P3128 [USACO15DEC]Max Flow P

        题意简述： u->v 路径上的端点权值 +1、求最终最大权值

        d[i]：表示 i 号点到根节点这条路径每个点要加的值。

        这样每个点的真实值就是所有子节点的 d[] 之和（sum[i]）

        u->v 路径可以画成下面的样子：

        root - ...  - fa[uv] - uv/lca(u,v) - ... - u
                                   \ ... - v

        d[u]++,d[fa[uv]]-- 可以实现 u 到 uv 路径上的点都 +1

        d[v]++,d[uv]-- 可以实现 v 到 uv 路径上（不包括 uv ）的点都 +1。

        那么 u->v 路径上的端点权值 +1 对应的 d[] 修改就是：

        d[u]++;
d[v]++;
d[uv]--;
d[fa[uv]]--;

        最终再用一次 dfs 通过 d 数组还原出真实的值即可。

        #include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
const int MAXM = 50000;
int n, k;                // 点数、询问个数、根节点
vector<int> e[MAXN + 5]; // 存树
int fa[MAXN + 5];
int maxDep, dep[MAXN + 5];
void dfs(int u, int father)
{
    fa[u] = father;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == father)
            continue;
        dep[v] = dep[u] + 1;
        maxDep = max(maxDep, dep[v]);
        dfs(v, u);
    }
}
int lg2[MAXN + 5]; // 替代 log2(i)
int dp[MAXN][35];  // i号点的 2^j 层祖先
int lca(int u, int v)
{
    if (dep[u] > dep[v])
        swap(u, v); // 让u的高度不低于v
    if (u == v)
        return u;
    // 把 v 提到与 u 同样高度
    for (int j = lg2[n]; j >= 0; j--)
        if ((1 << j) <= dep[v] - dep[u])
        {
            v = dp[v][j];
        }
    if (u == v)
        return u;
    // 找lca
    for (int j = lg2[n]; j >= 0; j--)
        if (dp[v][j] != dp[u][j])
        {
            v = dp[v][j],
            u = dp[u][j];
        }
    return dp[u][0];
}
int d[MAXN + 5];
int sum[MAXN + 5];
void dfsdfs(int u, int fa)
{
    sum[u] = d[u];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfsdfs(v, u);
        sum[u] += sum[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //  输入
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 预处理：最大层数 maxDep、每个点的深度、记录父节点、log2[]、dp数组
    dep[1] = 1;
    maxDep = 1;
    dfs(1, 0);
    lg2[1] = 0;
    for (int i = 2; i <= n; i++)
        // i == 2^(log2(i-1)+1)
        if (i == (1 << (lg2[i - 1] + 1)))
            lg2[i] = lg2[i - 1] + 1;
        else
            lg2[i] = lg2[i - 1];
    for (int j = 0; j <= lg2[n]; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            // 求解 dp[i][j]
            if (j == 0)
                dp[i][j] = fa[i];
            else
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    // q 次询问
    while (k--)
    {
        int u, v;
        cin >> u >> v; // 求 lca(u,v)
        d[u]++;
        d[v]++;
        int uv = lca(u, v);
        d[uv]--;
        d[dp[uv][0]]--;
    }
    dfsdfs(1, 0);
    int maxSum = sum[1];
    for (int i = 1; i <= n; i++)
        maxSum = max(maxSum, sum[i]);
    cout << maxSum << "\n";
    return 0;
}
        • 0
          @ 2023-2-16 21:36:04

          三色二叉树

          #include <bits/stdc++.h>
using namespace std;
int e[512345][2];
int tot = 0;
string s;
//dp_max[i][j] 节点 i 染成 j 色后，最多多少个绿。
//0 绿、1 红、2 蓝、
int dp_max[512345][3];
int dp_min[512345][3];
void dfs_build(int now)
{
    tot++;
    if (s[now - 1] == '1')
    {
        e[now][0] = tot + 1;
        dfs_build(tot + 1);
    }
    if (s[now - 1] == '2')
    {
        e[now][0] = tot + 1;
        dfs_build(tot + 1);
        e[now][1] = tot + 1;
        dfs_build(tot + 1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    dfs_build(1);
    for (int i = tot; i >= 1; i--)
    {
        int l = e[i][0];
        int r = e[i][1];
        if (!l)
        {
            dp_max[i][0] = dp_min[i][0] = 1;
            dp_max[i][1] = dp_min[i][1] = 0;
            dp_max[i][2] = dp_min[i][2] = 0;
        }
        else if (!r)
        {
            dp_max[i][0] = max(dp_max[l][1], dp_max[l][2]) + 1;
            dp_max[i][1] = max(dp_max[l][0], dp_max[l][2]);
            dp_max[i][2] = max(dp_max[l][0], dp_max[l][1]);
            dp_min[i][0] = min(dp_min[l][1], dp_min[l][2]) + 1;
            dp_min[i][1] = min(dp_min[l][0], dp_min[l][2]);
            dp_min[i][2] = min(dp_min[l][0], dp_min[l][1]);
        }
        else
        {
            dp_max[i][0] = max(dp_max[l][1] + dp_max[r][2], dp_max[l][2] + dp_max[r][1]) + 1;
            dp_max[i][1] = max(dp_max[l][0] + dp_max[r][2], dp_max[l][2] + dp_max[r][0]);
            dp_max[i][2] = max(dp_max[l][0] + dp_max[r][1], dp_max[l][1] + dp_max[r][0]);
            dp_min[i][0] = min(dp_min[l][1] + dp_min[r][2], dp_min[l][2] + dp_min[r][1]) + 1;
            dp_min[i][1] = min(dp_min[l][0] + dp_min[r][2], dp_min[l][2] + dp_min[r][0]);
            dp_min[i][2] = min(dp_min[l][0] + dp_min[r][1], dp_min[l][1] + dp_min[r][0]);
        }
    }
    cout << max(max(dp_max[1][0], dp_max[1][1]), dp_max[1][2]) << " " << min(min(dp_min[1][0], dp_min[1][1]), dp_min[1][2]) << "\n";
    return 0;
}
          • 0
            @ 2023-2-16 21:33:23

            时态同步

            #include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500000 + 5;
int n, s;
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN];
int dp[MAXN], len[MAXN];
void dfs(int u, int fa)
{
    int maxLen = 0;
    dp[u] = 0;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].v;
        int w = e[u][i].w;
        if (v == fa)
            continue;
        dfs(v, u);
        maxLen = max(maxLen, w + len[v]);
        dp[u] += dp[v];
    }
    len[u] = maxLen;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].v;
        int w = e[u][i].w;
        if (v == fa)
            continue;
        dp[u] += maxLen - (w + len[v]);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    dfs(s, 0);
    cout << dp[s];
    return 0;
}
            • 0
              @ 2023-2-16 21:31:52

              有线电视网

              #include <bits/stdc++.h>
using namespace std;
struct Edge
{
    int v, w;
};
vector<Edge> e[3005];
int n, m;
int money[3005], mCnt;
int sz[3005];
//dp[i][j]: 子树i承载j位观众时最少亏多少钱
int dp[3005][3005];
void dfs_dp(int now)
{
    sz[now] = 0;
    dp[now][0] = 0;
    for (int i = 0; i < e[now].size(); i++)
    {
        int v = e[now][i].v;
        int w = e[now][i].w;
        dfs_dp(v);
        //now 之前的子树承载 j 用户
        for (int j = sz[now]; j >= 0; j--)
            //v 承载 k 用户
            for (int k = sz[v]; k >= 0; k--)
                dp[now][j + k] = min(dp[now][j + k], dp[now][j] + dp[v][k] + w);
        sz[now] += sz[v];
    }
    if (sz[now] == 0)
    {
        sz[now] = 1;
        dp[now][1] = -money[now];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n - m; i++)
    {
        int k, v, w;
        cin >> k;
        while (k--)
        {
            cin >> v >> w;
            e[i].push_back((Edge){v, w});
        }
    }
    for (int i = n - m + 1; i <= n; i++)
        cin >> money[i];
    memset(dp, 0x3f, sizeof(dp));
    dfs_dp(1);
    for (int i = m; i >= 0; i--)
    {
        if (dp[1][i] <= 0)
        {
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}
              • 0
                @ 2023-2-14 20:31:31

                二叉苹果树

                #include <bits/stdc++.h>
using namespace std;
int n, q;
int dp[105][105]; // dp[i][j] 子树i保留j条边最多多少苹果
struct Edge
{
    int v, w;
};
vector<Edge> e[105];
void dfs(int u, int fa)
{
    dp[u][0] = 0;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].v;
        int w = e[u][i].w;
        if (v == fa)
            continue;
        dfs(v, u);
        //从大往小枚举，保证 dp[u][j+k+1] 计算时，dp[u][j] 没有被求过
        for (int j = q; j >= 0; j--) // u之前保留j条边
        {
            for (int k = 0; k + j + 1 <= q; k++) // v提供多少条边
            {
                //隐含条件：选择v下面的边时，u-v 之间的这条边包括进来了
                dp[u][j + k + 1] = max(dp[u][j + k + 1],
                                       dp[u][j] + dp[v][k] + w);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    dfs(1, 0);
    /*
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= q; j++)
            cout << dp[i][j] << " ";
        cout << "\n";
    }
    */
    cout << dp[1][q] << "\n";
    return 0;
}
                • 0
                  @ 2023-2-14 20:10:35

                  战略游戏

                  #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1500;
int n;
vector<int> e[MAXN + 5];
int dp[MAXN+5][2];
void dfs(int u, int fa)
{
	dp[u][0]=0;
	dp[u][1]=1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
        dp[u][1]+=min(dp[v][0],dp[v][1]);
        dp[u][0]+=dp[v][1];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int u, k, v;
        cin >> u >> k;
        u++;
        for (int i = 1; i <= k; i++)
        {
            cin >> v;
            v++;
            e[u].push_back(v);
        }
    }
    dfs(1, 0);
    cout<<min(dp[1][0],dp[1][1])<<endl;
    return 0;
}
                  • 0
                    @ 2023-2-11 18:10:19

                    没有上司的舞会

                    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 6000;
int n, root;
int r[MAXN + 5];
vector<int> e[MAXN + 5];
int dp[MAXN + 5][2]; //dp[i][0]:i不参加、dp[i][1]:i参加
void dfs(int u)
{
    dp[u][0] = 0;
    dp[u][1] = r[u];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> r[i];
    root = n * (n + 1) / 2;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> v >> u;
        root -= v;
        e[u].push_back(v);
    }
    dfs(root);
    cout<<max(dp[root][0],dp[root][1])<<endl;
    return 0;
}
                    • 0
                      @ 2023-2-11 18:09:38

                      最大子树和

                      #include<bits/stdc++.h>
using namespace std;
int n;
int a[16000+5];
vector<int> e[16000+5];
int dp[16000+5];//dp[i] i这棵子树的最大联通块的和（必须选择i）
void dfs(int u,int fa){
	dp[u] = a[u];
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa)
			continue;
		dfs(v,u);
		if(dp[v]>0)
			dp[u]+=dp[v];
	}
} 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0); 
	int ans=dp[1];
	for(int i=2;i<=n;i++)
		ans=max(ans,dp[i]);
	cout<<ans<<"\n";
	return 0;
}
                      • 1

                      树上差分与树形DP - 扩展题单

                      信息

                      ID
                      1220
                      时间
                      1000ms
                      内存
                      256MiB
                      难度
                      1
                      标签
                      递交数
                      29
                      已通过
                      26
                      上传者
                      1. 评测队列
                      2. 服务状态
                      3. 兼容模式
                      4. 主题
                      2. 陕ICP备2022006801号-1
                      3. Worker 0, 45ms
                      4. Powered by Hydro v4.17.3 Community, Modified by 33DAI