DP选讲
讲了蛮多题的,也没时间做。就先把思路整理一下,以后有时间再做吧(flag高高挂起)
DP杂题
AGC034E
首先枚举一个节点作为根,问题就变成了:每次选择不是祖先-后代关系的两个点向上跳跃,看能不能把所有点跳跃到根节点。
这里涉及到一个经典的模型:有很多个集合,每次选择两个不同的集合,各自消掉一个元素,看能不能消完。
这里有一个结论:当中最大的集合为时,有
- 当,可以完全消除(和为偶数一个不剩,和为奇数只留一个)。
- 当,会剩下个无法消除。
这个结论可以这样证明:
- 出现第一种情况时,拿前两大的来消,消一次后依旧是第一种情况。(最大的和除最大的之外的和共同减小1)
- 出现第二种情况时,拿最大的消掉其他所有的即可。
那么有了这个结论,又有了根节点,那我们就可以对全树进行DP。因为这里的“消除”是带权值的(一个点要被“消”多次才会到达根节点,这个次数就是他的深度。)后文说的“点”均为虚点,一个点产生的虚点个数为他距离目标的长度。
令为当前树中的子树中,最多能消掉多少对点。我们令为的儿子集合,令。然后我们就可以根据上面那个结论得到转移的方程:
- 当, 。
- 当,
其实这个东西可以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
我们首先考虑对于任意一个数,数字对答案的贡献:
那么任意一个数对答案的贡献就是:
因为后面这个“限制数字固定为多少”,数位DP不太好求。所以我们考虑把他化成“限制数字大于多少”的形式。
然后我们发现现在后面这一部分变成了“数字大于等于的贡献”。于是我们可以对于每一个,利用数位DP单独计算一次贡献。
令代表枚举到第位,大于等于的数字有个,当前枚举的数字前缀是不是和上界重合时,小于等于X的数有多少个。
转移方程:
贴近上界的情况类似,特殊处理一下即可。
然后我们知道,所有“大于等于K”的数,都是被排列在新生成数的最后几位。所以通过这种方法求的一定是一串前导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个以上字符串的公共子序列。
我们定义二元组代表开头为,后面加上的一个子序列得到的子序列的个数。令字符串集合为那么初始化的时候有:。然后每次转移就考虑三种决策:
- 直接结束,将置为
- 将中的第一个1及其之前部分删除,加上1
- 将中的第一个0及其之前部分删除,加上0
然后我们扫描所有,在计数器的部分中寻找字典序列最小的即可。因为我们每次选择转移都选择的是第一个规定的字符,是按照子序列自动机的方式进行的转移。因为一个子序列在子序列自动机上的路径唯一,所以我们这种方法是不会算重的。
一共有种状态,进过预处理之后的转移是的。因此复杂度是
#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
我们可以把权值离散化。因为每个人在哪里洗车,只和区间中的最小值有关。所以我们考虑区间DP。
令为区间内,最小值为的最大收益。
那么我们的转移方程就是:。其中我们为最小值对应的坐标,代表在中,和有交的消费者个数。
所以转移复杂度是。前两个是枚举区间用到的,然后我们用的时间枚举一个最小值位置,然后用的时间计算出。然后我们再花的时间枚举两边的最小值是多少即可。
BZOJ2616
考虑每次找出当前棋盘中最矮的一个,然后将长为当前棋盘长度,高为最矮的高度的一个矩形“子棋盘”拆出来,作为当前笛卡尔树节点。然后将选定最矮那一列左右分成两个棋盘,作为当前笛卡尔树节点的左右儿子。
然后就可以考虑DP了。
令为的子树内,选择个点的方案数。