2024.2.4+2024.2.5

刘梓轩2010 · 2024-02-04 10:37:13 · 个人记录

DP

前置

最难点在于看出来是dp

(易与网络流混淆)

状态，转移，初始化

状态最基础(关键)

转移：状态之间的关系（简单）

初始化：状态的边界条件

设计状态：找到题目中所有在变化的量，将其作为状态（先塞再删）

不能用状态以外的信息

eg：数字三角形上，求走到最后%100最大为多少

[tyvj-1076] - 数字三角形2

不同于数字三角形原题，目前最优不保证一直最优

（所有dp的错误都来自状态不够）

所以再加一维状态

表示在 ( i , j ) 位置上,模数为 k 是否可能

转移方式

用别人求自己

用自己求别人

（博弈论dp）记忆化搜索（不好for的时候）

分类

有模版：背包，区间，树形，数位，状压，插头（不考），排列，博弈论

一般dp(更难)

eg:Paint Pearls

cin>>n;
f[1][0]=1;
for(int i=1;i<=n;i++)
{
    for(int j=0;j<=i*(i-1)/2;j++)//逆序对数最多为每个数都 与后面的数 形成逆序对的情况 
    {
        for(int k=0;k<=i;k++)
        {
            f[i+1][j+i-k]+=f[i][j];
        }
    }
}

针对本题优化： j:0/1

 cin>>n;
f[1][0]=1;
for(int i=1;i<=n;i++)
{
    for(int j=0;j<=1;j++)
    {
        for(int k=0;k<=i;k++)
        {
            f[i+1][(j+i-k)&1]+=f[i][j];
        }
    }
}

可优化到O(n)

O(1)

完全背包

状态一样，枚举个数

优化

由于不关心到底选了多少个

所以f_{i,j} 不从 f_{i-1,j-v_i} 转移，从 f_{i,j-v_i} 转移

将斜线拆为一竖一横

for(int i=1;i<=n;i--)
{
    for(int j=0;j<m;j++)
        {
        f[i][j]=f[i-1][j];
        if(j>=v[i])
        {
            f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    }
}

多重背包

每个物品有限个

（想办法将未知变为已知）

（可能的出新题方法：TA+TB=TC）

将物品个数进行二进制拆分

eg: 17=1+2+4+8+2

转化为01背包

复杂度：O(nm\log_2{n})

for(int i=1;i<=cnt;i++)
{
    int tiji,jiazhi,geshu;
    cin>>tiji>>jiazhi>>geshu;
    int k=1;
    while(k<=geshu)
    {
        n++;
        v[n]=tiji*k;
        w[n]=jiazhi*k;
        geshu-=k;
        k*=2;
    }
    if(geshu!=0)
    {
        n++;
        v[n]=tiji*geshu;
        w[n]=jiazhi*geshu;
    }
}

P4095 [HEOI2013] Eden 的新背包问题

正着跑一遍，倒着跑一遍，每次不算这个物品的区间，将两个区间拼起来

数位dp

eg给出l,r，求出[l,r]有几个数(不能 r-l+1 )

转移方法

从高位开始，一位一位填数,枚举下一位填什么

状态

方法

扔掉左端点和右端点

关键词（不绝对）

子序列

树形dp

在树上做的dp

eg 给定n个点的树，求这棵树有多少点

暴力求肯定炸

我们只关心一条边经过了几次

求最长路，次长路即可

vector<Node> G[N];
int f[N];//最长 
int g[N];//次长距离 
void dfs(int u,int fa)
{
    f[u]=0;
    g[u]=0;
    for(auto x:G[u])
    {
        v=x.v;
        w=x.w;
        if(v==fa)
        {
            continue;
        }
        dfs(v,u);
        int dis=f[v]+w;
        if(dis>f[u])
        {
            g[u]=f[u];
            f[u]=dis;
        }
        else if(dis>g[u])
        {
            g[u]=dis;
        }
    }
}

eg 求最大独立集

最大独立集：选出尽量多的点，使得点与点之间不相邻

P1352 没有上司的舞会

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=6e3+5;
short r[N];
int f[N][2];
int n;
vector<int> g[N];
int ind[N];
int s;
void dfs(int u,int fa)
{
    f[u][1]=r[u];
    f[u][0]=0;
    for(auto v:g[u])
    {
        if(v==fa)
        {
            continue;
        }
        dfs(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        //u不来,v可来可不来 
        f[u][1]+=f[v][0];
        //u来,v一定不来 
    }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>r[i];
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        g[y].push_back(x);
        ind[x]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==0)
        {
            s=i;
            break;
        }
    }
    dfs(s,0);
    cout<<max(f[s][1],f[s][0]);
    return 0;
}

保安站岗

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1510;
const int INF=0x3f3f3f3f;
int n;
int r[N];
int m;
int f[N][3];
//f[i][0] 表示 该节点不选 孩子看 
//f[i][1] 表示 该节点选 
//f[i][2] 表示 该节点不选 父亲看 
vector<int > g[N];
void dfs(int u, int fa)
{
    f[u][1]=r[u];
    bool flag=0;
    int tmp = INF;
    for(auto v : g[u])
    {
        if(v == fa)
        {
            continue;
        }
        dfs(v, u);
        f[u][1] += min({f[v][0], f[v][1], f[v][2]});
        f[u][2] += min(f[v][0], f[v][1]);
        if(f[v][1] <= f[v][0])
        {
            flag=1;
        }
        else
        {
            tmp = min(tmp, f[v][1] - f[v][0]);
        }
        f[u][0] += min(f[v][0], f[v][1]);
    }
    if(flag == false)
    {
        f[u][0] += tmp;
    }
   //f[u][0]也可通过辅助数组记录前i个儿子中是否有保安的情况最小花费
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        cin>>r[x];
        cin>>m;
        for(int j=1;j<=m;j++)
        {
            int y;
            cin>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }
    dfs(1,0);
    cout<<min(f[1][0],f[1][1]);
    return 0;
}

状压dp

eg 旅行商问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int n;
double f[1<<20][20];//f[s][i] 当前在i点 s代表那些点被走过 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            f[i][j]=1e20;
        }
    }
    f[1][0]=0;
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                for(int k=0;k<n;k++)
                {
                    if((1&(1<<k))==0)
                    {
                        f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+dis(j,k));
                    }
                }
            }
        }
    }
    double ans=1e20;
    for(int i=0;i<n;i++)
    {
        ans=min(ans,f[(1<<n)-1][i]);
    }
    cout<<ans;
    return 0;
}

特征

n不大

egCorn Fields G

矩阵快速幂

特征

1.f_{i} 只和 f_{i-1} 有关

转移系数 m 与 i 无关

但是本题为有向图，还有自环，最多拆成共有n+8n^2 个点

(n<=10^3,r<=20,t<=10^9)

从r入手

观察m ,发现如果将in的两维存反，m=in\times out

博弈论dp

eg A,B两人,有数n，两人有4种操作,将n 减1,2,4,8

sg定理

特征（第二类）

多个游戏

做法

• sg值dp

• 转化为Nim石子游戏问题

经典例题 Nim石子游戏问题

将n 堆石子数异或起来

番外

“我们今天不讲（插头dp），又不考，（插头dp）如果出了就尽情骂出题人就行了，不用克制，不用收敛”

英文题面读不懂怎么办？ fanyi.baidu.com

比今年，啊不，去年noipT4简单，今年题是啥我还不知道，我也不知道我还出不出题，我已经有几年没出题了

"同学们私聊我问问题的时候注意一下是不是开了陌生人不能发消息"

"种国王"

"时间和空间都比较炸裂"