头像

秦淮岸灯火阑珊

会回来的




离线:6个月前


最近来访(11151)
用户头像
wnznw
用户头像
闻歌
用户头像
wrtgj
用户头像
ShowMeTheCode
用户头像
摩西摩西_8
用户头像
I.H.S.
用户头像
Tiwwp8n24
用户头像
hiccgoal
用户头像
Silvervale
用户头像
韩han
用户头像
nixnix
用户头像
冯子上
用户头像
jasonho
用户头像
布克波波
用户头像
想吃好吃的
用户头像
MOLL
用户头像
甘廿甘廿
用户头像
小时琦
用户头像
嘎嘎嘎嘎嘎嘎嘎
用户头像
孤灯


秦淮岸灯火阑珊
2021-04-21 12:17

原题链接
更好的阅读体验

算法解析

首先观察数据范围

我们发现,$n \le 10$

这是状态压缩DP的典型数据范围

接着我们看本题是一个棋盘,然后一个点的放置受到其他点的限制

那么我们可以确定本题为棋盘类型的状态压缩

显然每一行的状态是必须储存下来的

问题是,这里有m行,那么这么多数据,我们难道要全部压缩进来吗?

完全不能!

那么我们来观察一个点的状态限制

攻击状态.png

红色是我们当前放置的点,而橙色是我们不能放置的点。

根据上面的图片显示,一个点在不考虑下面摆放的前提下,我们只需要考虑上面两行的状态。

我们不妨设f[2][a][b]表示当前行,状态为a,上一行的状态为b

那么在这里,我们状态转移就是

f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+cnt[a])

在这里cnt[a]表示状态为a,放置了多少个士兵

接下来我们需要考虑状态限制的具体表示

  1. 放置士兵的格子,左边2格,右边2格上不能有士兵
  2. 放置士兵的格子,上面一行,左边1格,右边1格不能放置士兵
  3. 放置士兵的格子,上上行不能放置士兵

然后一个状态,有10位,那么存放大小得为1024

但是根据同一行,左右2格上不能放置的规定(也就是第一条)

我们发现最后合法的状态,一共有169个状态

所以我们不妨把这些合法状态编号,然后用编号来表示对应的状态

这样可以压缩状态,保证不超内存

最后记得一点:循环枚举时候,遇到不合法的状态,直接跳过,不要浪费时间。(具体看代码实现)

易错点总结:
1. 没有考虑上上行的状态
2. 状态没有压缩好,导致MLE

代码解析

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int f[2][220][220],cnt[210],n,m,pre[110],ok[220],qs;//其实可以用滚动数组
inline int check1(int a)
{
    bool ok1=a & (a<<2);//判断a有没有自己打自己的
    return ok1;
}
inline int check2(int a,int b)//a为这一行状态,b为上一行状态
{
    bool ok1=b & (a<<1);//来自右边的
    bool ok2=b & (a>>1);//来自左边的
    return (ok1 | ok2);
}
int count(int x)//统计这种状态下,放置点的数量
{
    int ans=0;
    while(x)
    {
        ans+=(x&1);
        x>>=1;
    }
    return ans;
}
inline void work()
{
    int ans=0;
    for(int i=1; i<=m; i++)
    {
        for(int s=0 ; s<qs; s++)//当前行
        {
            int now=ok[s];
            if (now & pre[i])//自判 &子集判断
                continue;
            for(int j=0; j<qs; j++)
            {
                int last=ok[j];
                if (last & pre[i-1])//判断状态是否自身合法,可以放置
                    continue;
                if (check2(now,last))//上下对打
                    continue;
                for(int k=0; k<qs; k++)
                {
                    int kk=ok[k];
                    if (kk & pre[i-2])//判断状态是否自身合法,可以放置
                        continue;
                    if (check2(last,kk))
                        continue;
                    if (now & kk)//自己和上上对打,很重要
                        continue;
                    f[i & 1][s][j]=max(f[i & 1][s][j],f[i-1 & 1][j][k]+cnt[s]);
                    //f[i][j][k]当前行为i,当前行状态的代号为j,上一行状态的代号为k
                }
            }
        }
    }
    for(int i=0; i<qs; i++)
        for(int j=0; j<qs; j++)
            ans=max(ans,f[m & 1][i][j]);
    printf("%d\n",ans);
}
inline void init()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        memset(pre,0,sizeof(pre));
        qs=0;
        for(int i=0; i<1<<n; i++)
            if(!check1(i))//找到满足自己不打自己的状态们
                ok[qs]=i,cnt[qs]=count(i),++qs;//统计子集状态
        int now=0;
        for(int i=1; i<=m; i++)
            for(int j=0; j<n; j++)
            {
                scanf("%d",&now);
                if (now==0)
                    pre[i]+=(1<<j);//构造不可以放士兵的状态
            }
        work();
    }
}
signed main()
{
    init();
    return 0;
}


活动打卡代码 AcWing 1128. 信使

秦淮岸灯火阑珊
2021-03-26 12:19
#include <bits/stdc++.h>
using namespace std;
const int N=2200;
int edge[N],ver[N],Next[N],head[N],tot;
int n,m,k,dis[N],vis[N];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
inline void spfa(int st)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(st);
    dis[st]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=head[now]; i; i=Next[i])
        {
            int y=edge[i];
            if (dis[now]+ver[i]<dis[y])
            {
                dis[y]=dis[now]+ver[i];
                if (!vis[y])
                {
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    spfa(1);
    int ans=0;
    for(int i=1; i<=n; i++)
        ans=max(ans,dis[i]);
    printf("%d\n",ans==1061109567?-1:ans);
}
signed main()
{
    init();
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

秦淮岸灯火阑珊
2021-03-26 12:13
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+20;
int n,m,edge[N],Next[N],head[N],ver[N],st,ed,tot,vis[N],dis[N];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
inline void spfa(int st)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    q.push(st);
    dis[st]=0;
    //上面都是初始化
    while(!q.empty())
    {
        int now=q.front();
        vis[now]=false;
        q.pop();
        for(int i=head[now]; i; i=Next[i])//遍历当前点可以抵达的点
        {
            int y=edge[i];
            if (dis[y]>dis[now]+ver[i])//这里是三角形
            {
                dis[y]=dis[now]+ver[i];//ver[i]表示now和y之间的边
                if (!vis[y])//如果本点已经在队列中,无需再加入一次
                {
                    q.push(y);
                    vis[y]=true;
                }
            }
        }
    }
}
inline void init()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);//这里是添加边
        add_edge(b,a,c);//本题是无向图,有双向边
    }
    spfa(st);//选择起点
    printf("%d\n",dis[ed]);//最终答案
}
signed main()
{
    init();
    return 0;
}

作者:秦淮岸灯火阑珊
链接:https://www.acwing.com/solution/content/28596/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 104. 货仓选址

秦淮岸灯火阑珊
2021-01-09 10:33
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    int sm=a[n/2+1];
    for (i=1;i<=n;i++)
        ans=ans+abs(a[i]-sm);
    cout<<ans;
    return 0;
}



秦淮岸灯火阑珊
2020-12-29 17:33

更好的阅读体验

题目描述

题目链接

有一棵点数为 $N$ 的树,树边有边权。

给你一个在 $0 \sim N$ 之内的正整数 $K$,你要在这棵树中选择 $K$ 个点,将其染成黑色,并将其他的 $N-K$ 个点染成白色。

将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少!

输入格式

第一行两个整数 $N,K$。

接下来 $N-1$ 行每行三个正整数 $fr,to,dis$,表示该树中存在一条长度为 $dis$ 的边 $(fr,to)$。

输入保证所有点之间是联通的。

输出格式

输出一个正整数,表示收益的最大值。

数据范围

$1 \le N \le 2000$,
$0 \le K \le N$

输入样例:

5 2
1 2 3
1 5 1
2 3 1
2 4 2

输出样例:

17

样例解释

将点 $1,2$ 染黑就能获得最大收益。

解题报告

题意理解

原题很清晰,没法简析了。

探索算法

有一说一,第一眼看到这道题目,博主是真的没有认为这道题目的是一个树形DP。

但是,染色的题目,加上最值问题的要求,还是和树形DP联系很大。

那么我们为什么很难看出来呢?可能是因为我太菜了

因为我们的关注点,是一个点,它所提供的贡献。

而不是一条边,所提供的贡献

其实这也是一个难想&常见的思路。

对于树上的题目,求贡献,不是点,就是边至少提高组范畴是这样的

那么如果说,我们按照边来思考的话,这道题目的转移方程还是很有意思的。

算法解析

类似于状态压缩动态规划,树形DP的题目,状态设计是极为重要的一步。

那么如何设计状态呢?

既然上面,我们说了,要按照边来算贡献,那么我们就先来分析边,是如何提供贡献的?

对于一条边而言,他可以提供的贡献,来自于两个节点之间的路径有它,也就是经过它:

  1. 左右两边黑色节点提供的。(自己子树内的黑色节点 $ \times $ 子树外黑色节点。
  2. 左右两边白色节点提供的。(自己子树内的白色节点 $ \times $ 子树外白色节点。

那么此时我们需要确定状态了

$
f[x][i] 表示节点x它到父亲节点的这条边,他的子树有i个染黑节点,此时提供的最大贡献
$

那么对于一个节点他有多少个染黑节点呢?

不知道?

那么枚举吧。

于是本题成了一个树形背包。

每个节点他的子树有多少个黑色节点(体积),然后算出这条边对答案的贡献(价值)

black_sum=s*(k-s)
white_sum=(Size[y]-s)*((n-Size[y])-(k-s)) 

$s$为当前节点他的子树有多少个染成黑色的节点

$k$为题目给出的有k个节点染成黑色

$Size[y]$表示当前节点他的子树一共有多少个节点

因此本题就这么愉快的解决了,在这里默认,树形背包DP大家都会吧。。。

如果不会的话,可以参照Acwing我曾经的背包DP的讲义。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=2100;
int n,k,head[N<<1],edge[N<<1],Next[N<<1],tot,Size[N];
long long f[N][N],ver[N<<1];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
void tree_DP(int x,int fa)
{
    Size[x]=1;
    memset(f[x],-1,sizeof(f[x]));
    f[x][0]=f[x][1]=0;
    for(int i=head[x]; i; i=Next[i])//visit its sons
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        tree_DP(y,x);//visit the son
        Size[x]+=Size[y];//count the Size of the tree
    }
    //Next part is the DP whose kind is knapsack.
    for(int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        for(int j=min(k,Size[x]); j>=0; j--)//choose black nodes whose number is j
        {
            for(int s=0; s<=min(j,Size[y]); s++)
                if (~f[x][j-s])
                {
                    long long black_sum=s*(k-s);//balck pairs
                    long long white_sum=(Size[y]-s)*((n-Size[y])-(k-s));//white pairs
                    f[x][j]=max(f[x][j],f[x][j-s]+f[y][s]+(black_sum+white_sum)*ver[i]);
                }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    tree_DP(1,0);
    printf("%lld\n",f[1][k]);
}
signed main()
{
    init();
    return 0;
}



秦淮岸灯火阑珊
2020-12-29 16:52

更好的阅读体验

谢谢 @Yimingli 找到这篇博文的bug

题目描述

题目链接

一棵二叉树可以按照如下规则表示成一个由 $0、1、2$ 组成的字符序列,我们称之为 “二叉树序列 $S$”:

$S=
\begin{cases}
0 \ \ \ \ \ \ \ \ \ \ 表示该树没有子节点 \newline
1S_1 \ \ \ \ \ \ 表示该树有一个子节点,S_1 为其子树的二叉树序列 \newline
2S_1S_2 \ \ 表示该树有两个子节点,S_1 和 S_2 分别表示其两个子树的二叉树序列
\end{cases}$

例如,下图所表示的二叉树可以用二叉树序列 $S=21200110$ 来表示。

123

你的任务是要对一棵二叉树的节点进行染色。

每个节点可以被染成红色、绿色或蓝色。

并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列,请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入格式

仅有一行,表示一个二叉树序列。

输出格式

只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。

数据范围

输入序列长度不超过 $5 \times 10^5$。

输入样例:

1122002010

输出样例:

5 2

解题报告

题意理解

每一个节点可以染三种颜色,红黄绿三种,要求父子节点颜色不同,而且左右儿子之间的颜色也要不同,问有多少个节点可以染色为绿色

探求算法

这是一棵

这棵树父子节点之前存在一定的限制关系

题目要求最值计数

根据上面的这些分析,我们不难得出本题需要用树形DP

算法分析

既然本题要用动态规划,那么我们得严格按照,以下顺序求解本题。

  1. 如何设计状态
  2. 状态如何转移

首先,我们来设计状态。

状态的属性必然是,可以染绿色的节点最多是多少。

接着,根据树形DP最常见的状态设计为:

一个节点,及其子树再满足条件的情况下,答案是多少?

所以我们不难设计出:

$$
f[i]为i及其子树,满足染色条件下,可以染成绿色的节点,最多为多少。
$$

这是初级的状态设计,我们还需要通过在分析状态转移的过程中,明确如何完善状态的设计。


接下来,设计状态转移。

分析题目的限制条件,来约束状态转移,使其满足不重复不遗漏。

接下来罗列一下约束条件:

  1. 父与子,节点颜色不同
  2. 左右儿子,两者之间,颜色不同

那么此时我们发现,如果还是初级的状态设计,是没有办法转移的。

因为我们并不知道每个节点的染色情况,那么也无法转移了。

所以我们需要优化状态设计

$$
f[i][0/1/2]表示节点i染色为红,黄,绿,在他和他的子树都满足染色条件下,染成绿色节点最多为多少。
$$

这样,我们就彻底完成了状态设计,那么接下来开始状态转移。

如果说:

$$
a表示左儿子的染色,son_a为左儿子序号 \\
b表示右儿子的染色,son_b为右儿子序号 \\
now表示当前节点的染色,i为当前节点序号
$$

那么显然
$$
a \neq b \neq now\\
$$

f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
//f[son_a][a]为左儿子选择颜色a,f[son_b][b]为右儿子选择颜色b
//f[son_a][b]为左儿子选择颜色b,f[son_b][a]为右儿子选择颜色a
//在这里a,b的定义不同于上面,指的是两种颜色,而且满足a,b不是当前节点的颜色
//f[x][i]为当前节点x选择颜色为i的绿色节点最大值,g[x][i]为最小值

如果说只有一个儿子节点,状态转移方程有所不同,但是和上面思路一样,具体可以直接看代码。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
char s[N];
int tot,tree[N][3],f[N][3],g[N][3],Size[N];
void dfs(int root)//Build the Tree
{
    Size[root]=s[root]-'0';//count the number of sons
    if (s[root]>='1')//left son
    {
        tree[root][0]=++tot;
        dfs(tot);
    }
    if (s[root]=='2')//right son
    {
        tree[root][1]=++tot;
        dfs(tot);
    }
}
void tree_DP(int x)
{
    if (Size[x]==0)//The node is a leaf node
    {
        f[x][2]=g[x][2]=1;
        return ;
    }
    for(int i=0; i<Size[x]; i++)//son
        tree_DP(tree[x][i]);
    for(int i=0; i<=2; i++)//color
    {
        int a=(i+1)%3,b=(i+2)%3;//other colors
        int son_a=tree[x][0],son_b=tree[x][1];//other sons
        if (Size[x]==1)//only a son
        {  

            f[x][i]=max(f[son_a][a],f[son_a][b]);
            g[x][i]=min(g[son_a][a],g[son_a][b]);
        }
        if (Size[x]==2)//two sons
        {
            f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
            g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
        }
        if (i==2)//the now node chooses the green color
            f[x][i]++,g[x][i]++;
        // printf("%d %d %d\n",x,f[x][i],g[x][i]);
    }
}
inline void out()//Output
{
    int ans_Min=1e9,ans_Max=0;
    for(int i=0; i<=2; i++)
    {
        ans_Min=min(ans_Min,g[1][i]);
        ans_Max=max(ans_Max,f[1][i]);
    }
    printf("%d %d\n",ans_Max,ans_Min);
}
inline void init()//Input
{
    scanf("%s",s+1);
    tot=1;
    dfs(1);
}
signed main()
{
    init();
    tree_DP(1);
    out();
    return 0;
}



秦淮岸灯火阑珊
2020-12-29 16:51

题目描述

题目链接

一棵二叉树可以按照如下规则表示成一个由 $0、1、2$ 组成的字符序列,我们称之为 “二叉树序列 $S$”:

$S=
\begin{cases}
0 \ \ \ \ \ \ \ \ \ \ 表示该树没有子节点 \newline
1S_1 \ \ \ \ \ \ 表示该树有一个子节点,S_1 为其子树的二叉树序列 \newline
2S_1S_2 \ \ 表示该树有两个子节点,S_1 和 S_2 分别表示其两个子树的二叉树序列
\end{cases}$

例如,下图所表示的二叉树可以用二叉树序列 $S=21200110$ 来表示。

123

你的任务是要对一棵二叉树的节点进行染色。

每个节点可以被染成红色、绿色或蓝色。

并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,那么这两个子节点的颜色也必须不相同。

给定一棵二叉树的二叉树序列,请求出这棵树中最多和最少有多少个点能够被染成绿色。

输入格式

仅有一行,表示一个二叉树序列。

输出格式

只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。

数据范围

输入序列长度不超过 $5 \times 10^5$。

输入样例:

1122002010

输出样例:

5 2

解题报告

题意理解

每一个节点可以染三种颜色,红黄绿三种,要求父子节点颜色不同,而且左右儿子之间的颜色也要不同,问有多少个节点可以染色为绿色

探求算法

这是一棵

这棵树父子节点之前存在一定的限制关系

题目要求最值计数

根据上面的这些分析,我们不难得出本题需要用树形DP

算法分析

既然本题要用动态规划,那么我们得严格按照,以下顺序求解本题。

  1. 如何设计状态
  2. 状态如何转移

首先,我们来设计状态。

状态的属性必然是,可以染绿色的节点最多是多少。

接着,根据树形DP最常见的状态设计为:

一个节点,及其子树再满足条件的情况下,答案是多少?

所以我们不难设计出:

$$
f[i]为i及其子树,满足染色条件下,可以染成绿色的节点,最多为多少。
$$

这是初级的状态设计,我们还需要通过在分析状态转移的过程中,明确如何完善状态的设计。


接下来,设计状态转移。

分析题目的限制条件,来约束状态转移,使其满足不重复不遗漏。

接下来罗列一下约束条件:

  1. 父与子,节点颜色不同
  2. 左右儿子,两者之间,颜色不同

那么此时我们发现,如果还是初级的状态设计,是没有办法转移的。

因为我们并不知道每个节点的染色情况,那么也无法转移了。

所以我们需要优化状态设计

$$
f[i][0/1/2]表示节点i染色为红,黄,绿,在他和他的子树都满足染色条件下,染成绿色节点最多为多少。
$$

这样,我们就彻底完成了状态设计,那么接下来开始状态转移。

如果说:

$$
a表示左儿子的染色,son_a为左儿子序号 \\
b表示右儿子的染色,son_b为右儿子序号 \\
now表示当前节点的染色,i为当前节点序号
$$

那么显然
$$
a \neq b \neq now\\
$$

f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
//f[son_a][a]为左儿子选择颜色a,f[son_b][b]为右儿子选择颜色b
//f[son_a][b]为左儿子选择颜色b,f[son_b][a]为右儿子选择颜色a
//在这里a,b的定义不同于上面,指的是两种颜色,而且满足a,b不是当前节点的颜色
//f[x][i]为当前节点x选择颜色为i的绿色节点最大值,g[x][i]为最小值

如果说只有一个儿子节点,状态转移方程有所不同,但是和上面思路一样,具体可以直接看代码。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
char s[N];
int tot,tree[N][3],f[N][3],g[N][3],Size[N];
void dfs(int root)//Build the Tree
{
    Size[root]=s[root]-'0';//count the number of sons
    if (s[root]>='1')//left son
    {
        tree[root][0]=++tot;
        dfs(tot);
    }
    if (s[root]=='2')//right son
    {
        tree[root][1]=++tot;
        dfs(tot);
    }
}
void tree_DP(int x)
{
    if (Size[x]==0)//The node is a leaf node
    {
        f[x][2]=g[x][2]=1;
        return ;
    }
    for(int i=0; i<Size[x]; i++)//son
        tree_DP(tree[x][i]);
    for(int i=0; i<=2; i++)//color
    {
        int a=(i+1)%3,b=(i+2)%3;//other colors
        int son_a=tree[x][0],son_b=tree[x][1];//other sons
        if (Size[x]==1)//only a son
        {  

            f[x][i]=max(f[son_a][a],f[son_a][b]);
            g[x][i]=min(g[son_a][a],g[son_a][b]);
        }
        if (Size[x]==2)//two sons
        {
            f[x][i]=max(f[son_a][a]+f[son_b][b],f[son_a][b]+f[son_b][a]);
            g[x][i]=min(g[son_a][a]+g[son_b][b],g[son_a][b]+g[son_b][a]);
        }
        if (i==2)//the now node chooses the green color
            f[x][i]++,g[x][i]++;
        // printf("%d %d %d\n",x,f[x][i],g[x][i]);
    }
}
inline void out()//Output
{
    int ans_Min=1e9,ans_Max=0;
    for(int i=0; i<=2; i++)
    {
        ans_Min=min(ans_Min,g[1][i]);
        ans_Max=max(ans_Max,f[1][i]);
    }
    printf("%d %d\n",ans_Max,ans_Min);
}
inline void init()//Input
{
    scanf("%s",s+1);
    tot=1;
    dfs(1);
}
signed main()
{
    init();
    tree_DP(1);
    out();
    return 0;
}

更好的阅读体验

题目描述

题目链接

有一棵点数为 $N$ 的树,树边有边权。

给你一个在 $0 \sim N$ 之内的正整数 $K$,你要在这棵树中选择 $K$ 个点,将其染成黑色,并将其他的 $N-K$ 个点染成白色。

将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少!

输入格式

第一行两个整数 $N,K$。

接下来 $N-1$ 行每行三个正整数 $fr,to,dis$,表示该树中存在一条长度为 $dis$ 的边 $(fr,to)$。

输入保证所有点之间是联通的。

输出格式

输出一个正整数,表示收益的最大值。

数据范围

$1 \le N \le 2000$,
$0 \le K \le N$

输入样例:

5 2
1 2 3
1 5 1
2 3 1
2 4 2

输出样例:

17

样例解释

将点 $1,2$ 染黑就能获得最大收益。

解题报告

题意理解

原题很清晰,没法简析了。

探索算法

有一说一,第一眼看到这道题目,博主是真的没有认为这道题目的是一个树形DP。

但是,染色的题目,加上最值问题的要求,还是和树形DP联系很大。

那么我们为什么很难看出来呢?可能是因为我太菜了

因为我们的关注点,是一个点,它所提供的贡献。

而不是一条边,所提供的贡献

其实这也是一个难想&常见的思路。

对于树上的题目,求贡献,不是点,就是边至少提高组范畴是这样的

那么如果说,我们按照边来思考的话,这道题目的转移方程还是很有意思的。

算法解析

类似于状态压缩动态规划,树形DP的题目,状态设计是极为重要的一步。

那么如何设计状态呢?

既然上面,我们说了,要按照边来算贡献,那么我们就先来分析边,是如何提供贡献的?

对于一条边而言,他可以提供的贡献,来自于两个节点之间的路径有它,也就是经过它:

  1. 左右两边黑色节点提供的。(自己子树内的黑色节点 $ \times $ 子树外黑色节点。
  2. 左右两边白色节点提供的。(自己子树内的白色节点 $ \times $ 子树外白色节点。

那么此时我们需要确定状态了

$
f[x][i] 表示节点x它到父亲节点的这条边,他的子树有i个染黑节点,此时提供的最大贡献
$

那么对于一个节点他有多少个染黑节点呢?

不知道?

那么枚举吧。

于是本题成了一个树形背包。

每个节点他的子树有多少个黑色节点(体积),然后算出这条边对答案的贡献(价值)

black_sum=s*(k-s)
white_sum=(Size[y]-s)*((n-Size[y])-(k-s)) 

$s$为当前节点他的子树有多少个染成黑色的节点

$k$为题目给出的有k个节点染成黑色

$Size[y]$表示当前节点他的子树一共有多少个节点

因此本题就这么愉快的解决了,在这里默认,树形背包DP大家都会吧。。。

如果不会的话,可以参照Acwing我曾经的背包DP的讲义。

参考代码

//My English is poor.The Code maybe have some grammer problems.
//To have a better Font display in Acwing.com,I must choose English.
#include <bits/stdc++.h>
using namespace std;
const int N=2100;
int n,k,head[N<<1],edge[N<<1],Next[N<<1],tot,Size[N];
long long f[N][N],ver[N<<1];
inline void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
void tree_DP(int x,int fa)
{
    Size[x]=1;
    memset(f[x],-1,sizeof(f[x]));
    f[x][0]=f[x][1]=0;
    for(int i=head[x]; i; i=Next[i])//visit its sons
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        tree_DP(y,x);//visit the son
        Size[x]+=Size[y];//count the Size of the tree
    }
    //Next part is the DP whose kind is knapsack.
    for(int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];
        if (y==fa)//its father
            continue;//can't visit its father node
        for(int j=min(k,Size[x]); j>=0; j--)//choose black nodes whose number is j
        {
            for(int s=0; s<=min(j,Size[y]); s++)
                if (~f[x][j-s])
                {
                    long long black_sum=s*(k-s);//balck pairs
                    long long white_sum=(Size[y]-s)*((n-Size[y])-(k-s));//white pairs
                    f[x][j]=max(f[x][j],f[x][j-s]+f[y][s]+(black_sum+white_sum)*ver[i]);
                }
        }
    }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    tree_DP(1,0);
    printf("%lld\n",f[1][k]);
}
signed main()
{
    init();
    return 0;
}


新鲜事 原文

秦淮岸灯火阑珊
2020-12-04 19:30
Enjoy OI


新鲜事 原文

秦淮岸灯火阑珊
2020-12-04 18:30
希望明天不自闭


新鲜事 原文

秦淮岸灯火阑珊
2020-11-07 09:35
CSP2020 RP++