首页 > 其他分享 >一些DP

一些DP

时间：2023-08-07 15:23:39浏览次数：38  
标签：sz int void back dfs push 一些 DP

P1273 有线电视网

树上背包的变形

\[f_{u, j + k} = \max_{v \in son(u)} f_{u, j} + f_{v, k} - w_{u,v} \]

这里写成 \(j + k\) 是为了和代码一致。

\(f_{u,j + k}\) 代表以 \(u\) 为根的子树中，选择了 \(j + k\) 个叶子结点的利润最大值。

\(w_{u, v}\) 代表 \(u\) 到 \(v\) 的边权。

然后就是很朴素的树上背包了，注意维护的是利润的最大值，有负数出现，需要初始化一下，详细见代码。

int n, m, w[N];
int sz[N], f[N][N], tmp[N], dep[N];
vector<pair<int, int>> e[N];
void dfs(int u)
{
    if(u >= n - m + 1)
    {
        f[u][1] = w[u];
        sz[u] = 1;
        return;
    }
    sz[u] = 0;
    for(auto [v, w] : e[u])
    {
        dfs(v);
        for(int i = 0; i <= sz[u] + sz[v]; i++)
            tmp[i] = f[u][i];
        for(int i = 0; i <= sz[u]; i++)
            for(int j = 0; j <= sz[v]; j++)
                tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j] - w);
        sz[u] += sz[v]; 
        for(int i = sz[u]; i >= 0; i--)
            f[u][i] = tmp[i];   
        // for(int i = sz[u]; i >= 0; i--)
        // {
        //     cout<<"U: "<<u<<"  V: "<<v<<"  sz[u]: "<<i<<"   f_u_sz: "<<f[u][i]<<'\n';
        // }
    }
}
void solve()
{       
    cin>>n>>m;
    for(int i = 1; i <= n - m; i++)
    {
        int k;  cin>>k;
        for(int j = 1; j <= k; j++)
        {
            int v, k;   cin>>v>>k;
            e[i].push_back({v, k});
        }
    }
    for(int i = n - m + 1; i <= n; i++)
        cin>>w[i];
    for(int i = 1; i <= n; i++)
    {
        f[i][0] = 0;
        for(int j = 1; j <= n; j++)
            f[i][j] = -inf;
    }

    dfs(1);
    for(int i = m; i >= 0; i--)
    {
        if(f[1][i] >= 0)
        {
            cout<<i<<'\n';
            return;
        }
    }
    return;
}

P2279 [HNOI2003] 消防局的设立

类似题目P2899 [USACO08JAN] Cell Phone Network G，不同处在于只覆盖相邻的


设 \(f_{u, i}\) 为以u为根的子树，消防局可以覆盖的范围，其中 \(i \in [0, 4]\)，分别代表可以覆盖到 \(dep_u + 2\), \(dep_u + 1\), \(dep_u\),\(dep_u - 1\),\(dep_u - 2\)层。

有转移方程

\[f_{u, 0} = 1 + \sum_{v \in son(u)} f_{v, 4} \\ f_{u, 1} = \sum_{v \in son(u)} f_{v, 3} - \max_{v \in son(u)} (f_{v,3} - f_{v, 0}) \\ f_{u, 2} = \sum_{v \in son(u)} f_{v, 2} - \max_{v \in son(u)} (f_{v, 2} - f_{v, 1}) \\ f_{u, 3} = \sum_{v \in son(u)} f_{v, 2} \\ f_{u, 4} = \sum_{v \in son(u)} f_{v, 3} \\ \]

注意！还需要在dp中对最小值进行转移

for(int i = 1; i <= 4; i++) f[u][i] = min(f[u][i - 1], f[u][i]);

int n;
int dep[N], f[N][10];    
vector<int> e[N];
void dfs(int u, int from)
{
    f[u][0] = 1;
    f[u][1] = f[u][2] = 1e8;
    int s1 = 0, s2 = 0;
    for(auto v : e[u])
    {
        if(v == from)   continue;  
        dfs(v, u); 
        f[u][0] = f[u][0] + f[v][4]; 
        s1 = s1 + f[v][3];
        s2 = s2 + f[v][2];
        f[u][3] = f[u][3] + f[v][2];
        f[u][4] = f[u][4] + f[v][3];
    }
    for(auto v : e[u])
    {
        if(v == from)   continue;  
        f[u][1] = min(s1 - f[v][3] + f[v][0], f[u][1]);
        f[u][2] = min(s2 - f[v][2] + f[v][1], f[u][2]);
    }
    for(int i = 1; i <= 4; i++)    f[u][i] = min(f[u][i - 1], f[u][i]);
}
void solve()
{       
    cin>>n;
    for(int v = 2; v <= n; v++)
    {
        int u;    cin>>u;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    cout<<min({f[1][0], f[1][1], f[1][2]})<<'\n';

    return;
}

P5662 [CSP-J2019] 纪念品

只要领悟到当天买的可以当天卖，求出今天买明天卖的最大值，就很简单了

int t, n, m, a[110][110], res;
int f[N];
void solve()
{       
    cin>>t>>n>>m;
    for(int i = 1; i <= t; i++)
        for(int j = 1; j <= n; j++)
            cin>>a[i][j];
    for(int k = 1; k < t; k++)
    {
	    memset(f, 0, sizeof f);
    	for(int i = 1; i <= n; i++)
    	{
	    	for(int j = a[k][i]; j <= m; j++)
	    		f[j] = max(f[j], f[j - a[k][i]] - a[k][i] + a[k + 1][i]);
	    }
	    m = max(f[m] + m, m);
    }
    cout<<m<<'\n';
    return;
}

image-20230807142317075

后面蓝色大部分都是分组背包+完全背包的题

CF219 Choosing Capital for Treeland

换根dp

\(1\) 为根结点, \(f_u\) 为以 \(u\) 为根的子树不需要反转的道路数量

\(g_v\) 为以 \(v\) 为整棵树的根结点，在以 \(1\) 为整棵树的根结点下 \(v\) 的父亲 \(u\) 的子树不需要反转的道路数量

有点绕，不知道意思清不清晰

f[u] = f[u] + f[v];
if(S.count({u, v})) f[u]++;

g[v] = g[u] + f[u] - f[v] + (S.count({v, u}) ? 1 : -1);

ll n, f[N], g[N];
vector<int> e[N];
set<pair<int, int>> S;
void dfs(int u, int from)
{
    for(auto v : e[u])
    {
        if(v == from)   continue;
        dfs(v, u);
        f[u] = f[u] + f[v];
        if(S.count({u, v})) f[u]++;
    } 
}
void dfs2(int u, int from)
{

    for(auto v : e[u])
    {
        if(v == from)   continue;
        g[v] = g[u] + f[u] - f[v] + (S.count({v, u}) ? 1 : -1);
        dfs2(v, u);        
    }
}


void solve()
{       

    cin>>n;
    for(int i = 1; i < n; i++)
    {
        int u, v;  cin>>u>>v;
        S.insert({u, v});
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    int miv = -1;
    vector<int> res;
    for(int u = 1; u <= n; u++)
    {
        if(f[u] + g[u] > miv)
        {
            miv = f[u] + g[u];
            res.clear();
        }
        if(f[u] + g[u] == miv)
            res.push_back(u);
    }
    cout<<n - miv - 1<<'\n';
    for(auto u : res)
        cout<<u<<' ';
    cout<<'\n';


    return;
}

CF767C Garland

\(sum = \sum _ {i = 1} ^ {n} a_i\)

\(f_u = a_u + \sum _ {v \in son(u)} f_v\)

直接dfs判断是否有 \(f_u = sum / 3\)

注意特判 \(u\) 的次数可以出现超过2次，因为有负数点权,记得把子树情况，和 sum % 3 != 0的特判

int n, f[N], w[N];
vector<int> e[N];
bool ok = true;
int res[N], cnt, sum;

void dfs(int u, int from)
{
    f[u] = w[u];
    for(auto v : e[u])
    {
        if(v == from)   continue;
        dfs(v, u);
        f[u] = f[u] + f[v];
    }
    if(f[u] == sum / 3)
    {
        f[u] = 0;
        res[++cnt] = u;
    }
    //f[u] = w[u];
}



void solve()
{       

    cin>>n;
    int root = 0;
    for(int i = 1; i <= n; i++)
    {
        int u;  cin>>u>>w[i];
        if(u == 0)  root = i;
        else e[u].push_back(i);
        sum += w[i];
    }
    //cout<<root<<'\n';
    dfs(root, 0);    
    if(sum % 3 != 0 || cnt <= 2)
    {
        cout<<-1<<'\n';
        return;
    }
    cout<<res[1]<<" "<<res[2]<<'\n';
    return;
}

ZJOI2007] 时态同步

深度小的增长到深度大的

\(f_u = \max_{v \in son(u)} f_v + w\)

\(res = \sum _ {u = 1} ^ {n} \sum _ {v \in son(u)} f_u - f_v - w\)

\(w\) 为 \(u\) 和 \(v\) 之间的边权

int n;
ll dep[N], f[N];    
vector<pair<int, int>> e[N];
ll res;
void dfs(int u, int from)
{
    for(auto [v, w] : e[u])
    {
        if(v == from)   continue;  
        dfs(v, u);         
        f[u] = max(f[u], f[v] + w);
    }
    for(auto [v, w] : e[u])
    {
        if(v == from)   continue;
        res += (f[u] - f[v] - w);
    }
    
}
void solve()
{       
    cin>>n;
    int s;  cin>>s;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;    cin>>u>>v>>w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(s, 0);
    cout<<res<<'\n';

    return;
}

P2279 [HNOI2003] 消防局的设立

不是最大独立集

1 个点可以覆盖其爷爷，父亲，自己，也可以被儿子，孙子覆盖

考虑各个点之间的覆盖转移

注意转移最小值

int n;
int dep[N], f[N][10];    
vector<int> e[N];
void dfs(int u, int from)
{
    f[u][0] = 1;
    f[u][1] = f[u][2] = 1e8;
    int s1 = 0, s2 = 0;
    for(auto v : e[u])
    {
        if(v == from)   continue;  
        dfs(v, u); 
        f[u][0] = f[u][0] + f[v][4]; 
        s1 = s1 + f[v][3];
        s2 = s2 + f[v][2];
        f[u][3] = f[u][3] + f[v][2];
        f[u][4] = f[u][4] + f[v][3];
    }
    for(auto v : e[u])
    {
        if(v == from)   continue;  
        f[u][1] = min(s1 - f[v][3] + f[v][0], f[u][1]);
        f[u][2] = min(s2 - f[v][2] + f[v][1], f[u][2]);
    }
    for(int i = 1; i <= 4; i++)    f[u][i] = min(f[u][i - 1], f[u][i]);
}
void solve()
{       
    cin>>n;
    for(int v = 2; v <= n; v++)
    {
        int u;    cin>>u;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    cout<<min({f[1][0], f[1][1], f[1][2]})<<'\n';

    return;
}

P2899 [USACO08JAN] Cell Phone Network G

思路同上题

P2986 [USACO10MAR] Great Cow Gathering G

换根dp

int n;
ll m,c[N], f[N], g[N], sz[N];
vector<pll> e[N];

void dfs1(int u,int fa)
{
    for(auto v : e[u])
    {
        if(v.fi == fa) continue;
        dfs1(v.fi, u);
        sz[u] += sz[v.fi];
        f[u] += f[v.fi] + sz[v.fi] * v.se;
    }
    sz[u] += c[u];
}
void dfs2(int u,int fa)
{
    for(auto v : e[u])
    {
        if(v.fi == fa) continue;
        g[v.fi] = g[u] + f[u] - f[v.fi] - sz[v.fi] * v.se + (m - sz[v.fi]) * v.se;
        dfs2(v.fi, u);
    }
}
void solve()
{   
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>c[i];
        m += c[i];
    }

    for(int i = 1; i < n; i++)
    {
        ll u, v, w; cin>>u>>v>>w;
        e[u].pb({v, w});
        e[v].pb({u, w});
    }
    dfs1(1, 0);
    dfs2(1, 0);
    ll ans = 1e18;
    for(int i = 1; i <= n; i++)
        ans = min(ans, f[i] + g[i]);
    cout<<ans<<endl;
    return;
}

P2585 [ZJOI2006] 三色二叉树

树形dp

我喜欢把树建出来再做

int n;
int f[N][4], g[N][4];
// R G B
vector<int> e[N];
string s;
int cnt = 1;
int k = 0;
void build(int u)
{

    if(s[k] == '2')
    {
        int l = ++cnt, r = ++cnt;
        e[u].push_back(l);
        e[u].push_back(r);
        k++;
        build(l);
        build(r);
    }
    else if(s[k] == '1')
    {
        int l = ++cnt;
        e[u].push_back(l);
        k++;
        build(l);
    }
    else if(s[k] == '0')
        k++;
}
void dfs(int u, int from)
{
    for(auto v : e[u])
    {
        if(v == from)   continue;  
        dfs(v, u); 
    }
    if(e[u].size() == 2)
    {
        int v1 = e[u][0], v2 = e[u][1];
        f[u][1] = max({f[v1][2] + f[v2][3], f[v1][3] + f[v2][2]});
        f[u][2] = max({f[v1][1] + f[v2][3], f[v1][3] + f[v2][1]}) + 1;
        f[u][3] = max({f[v1][1] + f[v2][2], f[v1][2] + f[v2][1]});

        g[u][1] = min({g[v1][2] + g[v2][3], g[v1][3] + g[v2][2]});
        g[u][2] = min({g[v1][1] + g[v2][3], g[v1][3] + g[v2][1]}) + 1;
        g[u][3] = min({g[v1][1] + g[v2][2], g[v1][2] + g[v2][1]});
    }
    else if(e[u].size() == 1)
    {
        int v = e[u][0];
        f[u][1] = max(f[v][2], f[v][3]);
        f[u][2] = max(f[v][1], f[v][3]) + 1;
        f[u][3] = max(f[v][1], f[v][2]);

        g[u][1] = min(g[v][2], g[v][3]);
        g[u][2] = min(g[v][1], g[v][3]) + 1;
        g[u][3] = min(g[v][1], g[v][2]);
    }
    else
    {
        f[u][2] = g[u][2] = 1;
    }
}
void solve()
{       
    
    cin>>s;
    build(1);
    n = cnt;
    dfs(1, 0);
    cout<<max({f[1][1], f[1][2], f[1][3]})<<" "<<min({g[1][1], g[1][2], g[1][3]})<<'\n';
    return;
}

P1272 重建道路

我的dp记录删除多少个点的最小代价，故复杂度是\(O(N^2)\)

int n, k;
vector<int> e[N];
int sz[N], f[N][N], tmp[N];
void dfs(int u, int from)
{
    f[u][0] = sz[u] = 0;
    for(auto v : e[u])
    {
        if(v == from)   continue;
        dfs(v, u);
        for(int i = 1; i <= sz[u] + sz[v]; i++)
            tmp[i] = inf;
        for(int i = 0; i <= sz[u]; i++)
        {
            for(int j = 0; j < sz[v]; j++)
                tmp[i + j] = min(tmp[i + j], f[u][i] + f[v][j]);
            tmp[i + sz[v]]  = min(tmp[i + sz[v]], f[u][i] + 1);
        }

        sz[u] += sz[v]; 
        for(int i = sz[u]; i >= 0; i--)
            f[u][i] = tmp[i];   
    }
    sz[u]++;
}
void solve()
{       
    cin>>n>>k;
    for(int i = 1; i < n; i++)
    {
        int u, v;   cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0); 
    int res = f[1][n - k];
    for(int i = 2; i <= n; i++)
         if(sz[i] >= k)
            res = min(f[i][sz[i] - k] + 1, res);
    cout<<res<<'\n';
    return;
}

P3177 [HAOI2015] 树上染色

一条边经过次数是 \(times = j \times (k - j) + (sz_v - j) \times (n - k + j - sz_v)\)

\(j\) 是子树的黑节点， \(sz_v\) 是子树的结点数量

const int N = 2e3 + 10;
const ll inf = 1ll << 60;
int n, k;
ll sz[N], w[N], f[N][N], tmp[N];
vector<pair<ll, ll>> e[N];
void dfs(int u, int from)
{
    f[u][0] = f[u][1] = 0;
    sz[u] = 1;
    for(auto [v, w] : e[u])
    {
        if(v == from)   continue;
        dfs(v, u);
        for(int i = 0; i <= sz[u] + sz[v]; i++)
            tmp[i] = -inf;
        for(int i = 0; i <= sz[u]; i++)
            for(int j = 0; j <= sz[v]; j++)
            {
                ll times = j * (k - j) + (sz[v] - j) * (n - k + j - sz[v]);
                tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j] + times * w);
            }
        sz[u] += sz[v]; 
        for(int i = sz[u]; i >= 0; i--)
            f[u][i] = tmp[i];   
    }
}

void solve()
{       
    cin>>n>>k;
    for(int i = 2; i <= n; i++)
    {
        int u, v, w;    cin>>u>>v>>w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1, 0);
    cout<<f[1][k]<<'\n';
    return;
}

标签：sz,int,void,back,dfs,push,一些,DP
From： https://www.cnblogs.com/magicat/p/17611545.html

相关文章

  • m基于QPSK+LDPC的载波同步和定时同步matlab性能仿真,包括Costas和gardner环,LDPC,四倍
    1.算法仿真效果matlab2022a仿真结果如下：本程序在博主之前的《基于QPSK的载波同步和定时同步性能仿真,包括Costas环的gardner环》算法基础上，加入了LDPC编译码进行仿真。2.算法涉及理论知识概要载波同步是相干解调的基础，不管对于模拟通信还是数字通信来说，只要是相干解调，接收端......
  • m基于QPSK+LDPC的载波同步和定时同步matlab性能仿真,包括Costas和gardner环,LDPC,四倍
    1.算法仿真效果matlab2022a仿真结果如下：   本程序在博主之前的 《基于QPSK的载波同步和定时同步性能仿真,包括Costas环的gardner环》 算法基础上，加入了LDPC编译码进行仿真。 2.算法涉及理论知识概要       载波同步是相干解调的基础，不管对于模拟通信还......
  • 星融元：DPU替代网络可视化专用设备实现业务报文深度处理
    网络可视化中的深度业务处理网络可视化场景中，通常需要将采集过来的数据经过深度业务处理后再交给后端分析系统。这些深度业务处理功能包括：传统的深度业务处理通常由带CPU的框式设备完成，但框式设备成本高、功耗大、扩展不够灵活的种种给客户带来了极大的困扰。DPU算力的池化应用Heli......
  • udp发送上位机（1）
    发送彩色视频RGB888时，在上位机，通过BGR2BGR565转换为16位数据，再传输时加上行号，在DMA里也要对读出的数据进行高低位的变换，组成RGB565格式如下图所示，在灰度图时将每帧刷新改为了每一行刷新，这是因为在彩色图像时，刷新一帧的时间大于2ms，而灰度时为0.7ms，这就会导致在刷新的时候，新的数据......
  • Linux 相关，个人整理的一些零碎笔记 2021-12-13
    df-lh接下来的四个字段Size、Used、Avail、及Use%分别是该分割区的容量、已使用的大小、剩下的大小、及使用的百分比du命令：查询文件或文件夹的磁盘使用空间如果当前目录下文件和文件夹很多使用不带参数du的命令，可以循环列出所有文件和文件夹所使用的空间。这对查看究竟是......
  • 前端 Vue 应该知道的一些东西，个人笔记 2021-11-26
    前端代码编写规范及es6常用语法命名规范文件夹名称，文件名称，组件名称，统一使用大驼峰或者小横线方式命名；组件文件名:list-item.vue.或者ListItem.vue;基础的无状态的通用组件加VBaseApp前缀BaseButtonAppButton在html中<base-button>或者<BaseButton>url路径名：小......
  • SOS DP（子集 DP）
    Part1：前置知识1、状压DP2、基本的位运算操作Part2：SOSDP(以下的内容大部分翻译至CF上的原文）1、例题引入给定一个含\(2^N\)个整数的集合\(A\)，我们需要计算：\(\forallx\subseteqA\)，\(x\)中所有元素\(i\)的\(A[i]\)的和，即求：\[F[mask]=\sum\limits_{i\subseteq......
  • FreeSWITCH添加自定义endpoint之媒体交互
    操作系统：CentOS7.6_x64FreeSWITCH版本：1.10.9 之前写过FreeSWITCH添加自定义endpoint的文章：https://www.cnblogs.com/MikeZhang/p/fsAddEndpoint20230528.html今天记录下endpoint媒体交互的过程并提供示例代码及相关资源下载，本文涉及示例代码和资源可从如下渠道获取：关......
  • 一些 tricks
    网络流最小割的可行边和必须边判定可行边：满流。在残余网络中找不到\(u\rightarrowv\)的路径。必须边：满流残余网络中源点能到入点,出点能到汇点。证明......
  • 一些 trick
    高次整除分块对\(\large\lfloor\frac{n}{i^2}\rfloor\)整除分块，\(\larger=\sqrt{\lfloor\frac{n}{\lfloor\frac{n}{l^2}\rfloor}\rfloor}\).容易发现对于\(i\len^{\frac{1}{3}}\)和\(i\gen^{\frac{1}{3}}\)，都只有\(n^\frac{1}{3}\)种取值，所以复杂度\(O(n^{\fr......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99