dp部分小结
背包
背包主要是模型的构建。
01背包
选与不选，且只能选一个。
for(int i=1;i<=n;i++){
for(int j=mt;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
完全背包
选与不选，可任意选。
for(int i=1;i<=n;i++){
for(int j=w[i];j<=mt;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
多重背包
选与不选，有数目限制。
- 考虑二进制拆分，讲一个大小为n的物品拆成O(logn)个物品
分组背包
选与不选，每组只能选一个
区间
枚举区间断点
\(
dp_{i,j}=max(dp_{i,k}+dp_{k+1,j})
\)
或
\(
dp_{i,j}=max(dp_{i,k-1}+dp_{k+1,j}+c_k)
\)
枚举区间最后一个点
数位
比较套路，只要确定好状态和限制就好了
ll dfs(int pos,int num,int lim,int d){
if(!pos)return num==d;
if(~dp[pos][num][lim][d])return dp[pos][num][lim][d];
int ma=lim?bit[pos]:1;
ll res=0;
for(int i=0;i<=ma;i++){
res+=dfs(pos-1,num+(i==1),lim&&i==ma,d);
}
return dp[pos][num][lim][d]=res;
}
状压
最好提前预处理合法状态
- 枚举子集
for(int i=st;i;i=(i-1)&st)
- 判断是否冲突
if((s1&s2)||(s1&(s2<<1))||((s1<<1)&s2))continue;