DP选讲

讲了蛮多题的，也没时间做。就先把思路整理一下，以后有时间再做吧（flag高高挂起）

DP杂题

AGC034E

首先枚举一个节点作为根，问题就变成了：每次选择不是祖先-后代关系的两个点向上跳跃，看能不能把所有点跳跃到根节点。

这里涉及到一个经典的模型：有很多个集合，每次选择两个不同的集合，各自消掉一个元素，看能不能消完。

这里有一个结论：当 $T$ 中最大的集合为 $k$ 时，有

当 $size(k)\leq \sum _{i\in T, i\ne k}size(i)$ ，可以完全消除（和为偶数一个不剩，和为奇数只留一个）。
当 $size(k)> \sum _{i\in T, i\ne k}size(i)$ ，会剩下 $size(k)- \sum _{i\in T, i\ne k}size(i)$ 个无法消除。

这个结论可以这样证明：

出现第一种情况时，拿前两大的来消，消一次后依旧是第一种情况。（最大的和除最大的之外的和共同减小1）
出现第二种情况时，拿最大的消掉其他所有的即可。

那么有了这个结论，又有了根节点，那我们就可以对全树进行DP。因为这里的“消除”是带权值的（一个点要被“消”多次才会到达根节点，这个次数就是他的深度。）后文说的“点”均为虚点，一个点产生的虚点个数为他距离目标的长度。

令 $F[i]$ 为当前树中 $i$ 的子树中，最多能消掉多少对点。我们令 $T$ 为 $i$ 的儿子集合，令 $sum=\sum _{j\in T, j\ne k}size(j)$ 。然后我们就可以根据上面那个结论得到转移的方程：

当 $size(k)\leq sum$ , $F[i]=\lfloor \frac{\sum_{j\in T}size(j)}{2}\rfloor$ 。
当 $size(k)> sum$ , $F[i]=sum+\lfloor \frac{min(size(k)-sum,2F[k])}{2}\rfloor$

其实这个东西可以DP，也可以搜一遍。都差不多。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
string a;
const int inf=1e9+1000;
const int maxn=2050;
int head[maxn],cnt;
struct gg {
    int u,v,next;
}side[maxn*2];
int size[maxn],sum,f[maxn],F[maxn],depth[maxn],dep_sum[maxn];
void insert(int u,int v) {
    side[++cnt]=(gg){u,v,head[u]};head[u]=cnt;
}
int ans=inf;
void init() {
    memset(F,0,sizeof(F));
    memset(size,0,sizeof(size));memset(f,0,sizeof(f));sum=0;
    memset(dep_sum,0,sizeof(dep_sum));
    for(int i=0;i<a.length();i++)size[i+1]=(a[i]=='1');
}
void dfs(int u,int fa,int d) {
    int tot=0,k=0,mx=-1;depth[u]=d;
    for(int i=head[u];i;i=side[i].next) {
        int v=side[i].v;if(v==fa)continue;
        dfs(v,u,d+1);
        dep_sum[u]+=dep_sum[v]+size[v];
        if(dep_sum[v]+size[v]>mx) {
            mx=dep_sum[v]+size[v];k=v;
        }
        size[u]+=size[v];
        tot+=dep_sum[v]+size[v];
    }
    int sum=tot-(dep_sum[k]+size[k]);
    if(mx<=sum)F[u]=tot/2;
    else F[u]=sum+min(mx-sum,2*F[k])/2;
}
int main() {
    ios::sync_with_stdio(0);
    int n;cin>>n>>a;
    for(int i=1,u,v;i<n;i++) {
        cin>>u>>v;
        insert(u,v);insert(v,u);
    }
    for(int i=1;i<=n;i++) {
        init();
        dfs(i,0,0);
        if(F[i]*2==dep_sum[i]) {
            ans=min(ans,dep_sum[i]);
        }
    }
    if(ans>=inf)printf("-1");
    else printf("%d",ans/2);
    return 0;
}

CF908G

我们首先考虑对于任意一个数，数字 $k$ 对答案的贡献： $c(k)=\sum_{digit[i]=k}10^i$

那么任意一个数对答案的贡献就是：

$ans=\sum_{k=1}^9 k\cdot c(k)$

因为后面这个“限制数字固定为多少”，数位DP不太好求。所以我们考虑把他化成“限制数字大于多少”的形式。

$ans=\sum_{k=1}^9 \sum_{i=k} ^9c(i)$

然后我们发现现在后面这一部分变成了“数字大于等于 $k$ 的贡献”。于是我们可以对于每一个 $k$ ，利用数位DP单独计算一次贡献。

令 $dp[i][j][0/1]$ 代表枚举到第 $i$ 位，大于等于 $k$ 的数字有 $j$ 个，当前枚举的数字前缀是不是和上界重合时，小于等于X的数有多少个。

转移方程： $dp[i][j][0]=(k-1)*dp[i-1][j][0]+(11-k)*dp[i-1][j-1][0]$

贴近上界的情况类似，特殊处理一下即可。

然后我们知道，所有“大于等于K”的数，都是被排列在新生成数的最后几位。所以通过这种方法求的 $\sum_{i=k} ^9c(i)$ 一定是一串前导0+一串1。这样答案就很好计算了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll dp[730][730][2];//前i位 符合条件的多少位 有没有贴到边界
char s[730];
ll ans=0;
int main() {
    scanf("%s",s+1);int len=strlen(s+1);
    for(int k=1;k<=9;k++){//限制大于等于k
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=s[1]-'0';i++) {
            bool ty2=(i>=k),ty3=(i==(s[1]-'0'));
            dp[1][ty2][ty3]+=1;
        }
        for(int i=1;i<len;i++) {
            for(int j=0;j<len;j++) {//符合条件多少位
                for(int st=0;st<=1;st++) {
                    if(!dp[i][j][st])continue;
                    for(int add=0;add<=(st?(s[i+1]-'0'):9);add++) {
                        dp[i+1][j+(add>=k)][st&&(add==(s[i+1]-'0'))]+=dp[i][j][st];
                        dp[i+1][j+(add>=k)][st&&(add==(s[i+1]-'0'))]%=mod;
                    }
                }
            }
        }
        ll tmp=0;
        for(int j=0;j<=len;j++) {
            ans+=(dp[len][j][0]+dp[len][j][1])%mod*tmp%mod;
            ans%=mod;tmp=(tmp*10)+1;tmp%=mod;
        }

    }
    printf("%lld",ans);
    return 0;
}

AGC024F

我们注意到字符串长度很短，但是个数很多。所以我们可以考虑暴力把所有子序列跑出来，然后看看哪些子序列是K个以上字符串的公共子序列。

我们定义二元组 $(S,T)$ 代表开头为 $S$ ，后面加上 $T$ 的一个子序列得到的子序列的个数。令字符串集合为 $P$ 那么初始化的时候有： $\forall T\in P,\space (\varnothing, T)=1$ 。然后每次转移就考虑三种决策：

直接结束，将 $T$ 置为 $empty$
将 $T$ 中的第一个1及其之前部分删除， $S$ 加上1
将 $T$ 中的第一个0及其之前部分删除， $S$ 加上0

然后我们扫描所有 $(S,\varnothing)$ ，在计数器 $\geq k$ 的部分中寻找字典序列最小的即可。因为我们每次选择转移都选择的是第一个规定的字符，是按照子序列自动机的方式进行的转移。因为一个子序列在子序列自动机上的路径唯一，所以我们这种方法是不会算重的。

一共有 $N\cdot 2^N$ 种状态，进过预处理之后的转移是 $O(1)$ 的。因此复杂度是 $N\cdot 2^N$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1<<22;
typedef long long ll;
typedef unsigned long long ull;
int data[maxn][21],n,k;
int mem[maxn*2];
char s[maxn];
int mx=1000000000,mxl=0;
void update(int sta,int nums,int len) {
    mem[sta|(1<<len)]+=nums;
    if(mem[sta|(1<<len)]>=k)
        if(mxl<len)mxl=len,mx=sta;
        else if(mxl==len)mx=min(mx,sta);

}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++) {
        scanf("%s",s);//len=2^i
        for(int j=0;j<(1<<i);j++) {
            int tmp=j;
            tmp|=1<<i;
            data[tmp][0]+=(s[j]=='1');
        }
    }
    for(int i=0;i<=n;i++) {//枚举已经拿了多少个
        for(int j=0;j<(1<<(n+1));j++) {//一共有n+1位
            if(!data[j][i])continue;//t-s
            ull s=j&((1<<i)-1),t=j>>i;int l=(32-__builtin_clz(t))-1;//有t多少位
            if(i)update(s,data[j][i],i);
            if(!l){continue;}
            t^=(1<<l);
            int first1=(32-(t?__builtin_clz(t):32));//第一个1在第几位
            unsigned int num=t<<(32-l);
            int first0=l?(l-((~num)?__builtin_clz(~num):l)):0;
            int newt,news;
            if(first1>0){//去掉一个1
                newt=t&((1<<first1)-1);
                newt|=(1<<first1-1);
                news=(s<<1)|1;
                data[(newt<<(i+1))|news][i+1]+=data[j][i];
            }
            if(first0>0){//去掉一个0
                newt=t&((1<<first0)-1);
                newt|=(1<<first0-1);
                news=(s<<1);
                data[(newt<<(i+1))|news][i+1]+=data[j][i];
            }
        }
    }
    if(mx==1000000000){puts("");return 0;}
    for(int i=mxl;i>=1;i--) {
        printf("%d",(mx&(1<<i-1))?1:0);
    }
    printf("\n");
    return 0;
}

笛卡尔树DP

所谓笛卡尔树DP，有些时候是真的要建出一个笛卡尔树，而有的时候只是一种枚举区间最小值，把问题分治成左右两半的思想。

BZOJ4380

我们可以把权值离散化。因为每个人在哪里洗车，只和区间 $[a_i,b_i]$ 中的最小值有关。所以我们考虑区间DP。

令 $F[i][j][x]$ 为区间 $[i,j]$ 内，最小值为 $x$ 的最大收益。

那么我们的转移方程就是： $F[i][j][x]=max(F[i][k-1][q_1\geq x],F[k+1][j][q_2\geq x])+x\cdot cost(i,k,j)$ 。其中我们 $k$ 为最小值 $x$ 对应的坐标， $cost(i,k,j)$ 代表在 $[i,j]$ 中，和 $k$ 有交的消费者个数。

所以转移复杂度是 $N^3\cdot (2N+M)$ 。前两个 $N$ 是枚举区间用到的，然后我们用 $O(N)$ 的时间枚举一个最小值位置 $k$ ，然后用 $O(M)$ 的时间计算出 $x\cdot cost(i,k,j)$ 。然后我们再花 $O(2N)$ 的时间枚举两边的最小值是多少即可。

BZOJ2616

考虑每次找出当前棋盘中最矮的一个，然后将长为当前棋盘长度，高为最矮的高度的一个矩形“子棋盘”拆出来，作为当前笛卡尔树节点。然后将选定最矮那一列左右分成两个棋盘，作为当前笛卡尔树节点的左右儿子。

然后就可以考虑DP了。

令 $F[u][k]$ 为 $u$ 的子树内，选择 $k$ 个点的方案数。