DP及DP优化1-171主机测评

数位DP

这个 DP 应该很好理解，就是把每个数位拆开单独处理，我们用例题讲解。

题目

P1836

P2657

P2518

P4067

P1836

这道题可以说是很好理解的一道模板题。

对于每种数字单独处理个数，时间复杂度： O(|n|) ，其中 |n| 表示的位数。

code：

ll f(ll n,ll x){
ll cnt=0,i;
for(i=1;n/i;i*=10){
cnt+=n/i/10*i-(x==0)*i;
if(x<n%(i*10)/i)
cnt+=i;
else
if(x==n%(i*10)/i)
cnt+=n%i+1;//求出单独的数值
}
return cnt;
}

int main(){
scanf("%lld",&r),l=1;
for(int i=0;i<=9;i++)
sum+=(f(r,i)-f(l-1,i))*i;//拆开处理
printf("%lld",sum);
}

P2657

数位 dp 开始，预处理位数为最高位为的 windy 数个数 $f_{i,j}$ 。

转移：

$f_{i,j}=f_{i-1,k}$ ，其中是非负整数 $k\\in [0,9]$ 且 $|k-j|\\ge 2$ 。

初始值：

$f_{1,i}=1$ ，其中i为非负整数 $i\\in[0,9]$ 。

void init(){
for(int i=0;i<=9;i++)
dp[1][i]=1;
for(int i=2;i<=10;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
if(abs(j-k)>=2)dp[i][j]+=dp[i-1][k];
}

int work(int x){
memset(a,0,sizeof(a));
int len=0,ans=0;
while(x)
a[++len]=x%10,x/=10;
for(int i=1;i<=len-1;i++)
for(int j=1;j<=9;j++)
ans+=dp[i][j];
for(int i=1;i<a[len];i++)
ans+=dp[len][i];
for(int i=len-1;i>=1;i–){
for(int j=0;j<=a[i]-1;j++)
if(abs(j-a[i+1])>=2)
ans+=dp[i][j];
if(abs(a[i+1]-a[i])<2)
break;
}
return ans;
}

int main(){
init(),cin>>l>>r,cout<<work(r+1)-work(l)<<endl;
}

P2518

对于一个数，把其中的 0 删掉，相当于把 0 放到了前面。

所以这个问题就是让我们求一下给我们的数的全排列比当前小的有几个。

我们假设 a_i 代表数字 $0\\sim 9$ 有几个。

那么用这些来表示全排列

(a_0+a_1+...+a_9)!/a_0!/a_1!/.../a_9!

但是这样的话，________表示我要爆炸。

所以我们要用高精度，所以我们在想想。

假如现在有个位置。

我们先把 0 放法放好 C(m,a_0) 。

之后就只有 m-a_0 个位置。

然后再放 1： C(m-a_0,a_1) 。

所以答案是 $C(m,a_0)\\times C(m-a_0,a_1)\\times...\\times C(m-a_0-a_1-..-a_8,a_9)$ 。

思路和数位 dp 差不多。

________表示我复活了。

ll cfb(){
ll ans=1;
int m=n;
for(int i=0;i<=9;i++)
if(a[i])
ans*=C(m,a[i]),m-=a[i];
return ans;
}

int main(){
while(cin>>c)
if(isdigit(c))
v[++n]=c-48,a[v[n]]++;
int nn=n;
for(int i=1;i<=nn;i++){
n–;
for(int j=0;j<v[i];j++)
if(a[j])
a[j]–,ans+=cfb(),a[j]++;
a[v[i]]–;
}
printf("%lld",ans);
}

P4067

如本题，先把题目转化为求 $\\sum^{n-1}_{i=0}{\\sum^{m-1}_{j=0}{[(i\\bigoplus j)\\ge k](i\\bigoplus j)}}-k\\sum^{n-1}_{i=0}{\\sum^{m-1}_{j=0}{[(i\\bigoplus j)\\ge k]}}$ 从高位到低位计算这两个值，记 $f_{i,a,b,c}$ 表示考虑到第位 a,b,c 分别表示当前值是否严格小于 n,m,k 。然后不难计算。

code：

for(int i=61;i;i–){
ll x=(n>>(i-1))&1,y=(m>>(i-1))&1,z=(k>>(i-1))&1;
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
for(int c=0;c<2;c++)
if(f[i+1][a][b][c]||g[i+1][a][b][c])
for(int xx=0;xx<2;xx++)
for(int yy=0;yy<2;yy++){
ll zz=xx^yy;
if((a&&x<xx)||(b&&y<yy)||(c&&z>zz))
continue;
ll aa(a&&(x==xx)),bb=(b&(y==yy)),cc=(c&(z==zz));
g[i][aa][bb][cc]+=g[i+1][a][b][c],
g[i][aa][bb][cc]%=p,
f[i][aa][bb][cc]+=f[i+1][a][b][c]+(zz-z+p)%p*((1ll<<(i-1))%p)%p*g[i+1][a][b][c]%p,
f[i][aa][bb][cc]%=p;
}
}

单调队列/单调栈优化

单调队列

就比如多重背包，没有学的可以学一下

单调栈

单调栈就是单调队列的特殊情况因此不讲。

题目

CF372C

设 $f_{i,j}$ 为第个烟花的时候在第个区间的最大开心值

推导方程

可见

$f_{i,j}=min(f_{i,j},f_{i-1,k}+b_i-|a_i-x|) \\\\ k\\in [max(1,j-t\\times d),min(n,j+t\\times d)]\\\\ t=t_i-t_{i-1}$

朴素 dp 方程还是很好推的

但是看时间复杂度最大 O(nm) 是无法通过的，空间复杂度也会爆。

先解决空间问题

容易想到滚动数组第一维i显然不需要存那么多，只需要存下当前和 i-1 即可，滚掉一维即可。

同时求 b_i-|a_i-x| 的最大值，同时 b_i 是一个固定的参数，我们可以转换成求 |a_i-x| 的最小值，这样可以更加方便操作。

我们枚举 $i\\rightarrow m$ 是无法优化的，同时枚举每个位置 $j\\rightarrow n$ 也是无法避免的，所以说我们想如何优化k的遍历，因为我们只需要通过在的范围内最小值来更新现在的 $f_{i,j}$ 。既然需要最小值，用单调队列优化即可。我们跑两遍，从 $1\\rightarrow n$ 和从 $n\\rightarrow 1$ 跑一遍，分别从右和从左更新 $f_{i,j}$ 。

code：

此题请自行书写。

凸包

凸函数，即导数存在单调性的函数。如果导数单调递减，称为上凸函数。如果导数单调递增，称为下凸函数。如 x^2 就是典型的下凸函数。如果一个多边形内，任意两点连线都不穿过该多边形，则该多边形为凸多边形。我们称一个凸多边形为凸包。给定一个点集，找到一个最小的凸多边形，使得其完全包含这个点集，这个凸多边形被称为该点集的凸包。很多时候也把一个凸多边形边上及其内部所有点组成的点集称为凸包。对于点集， $\\forall \\underset{a}{\\rightarrow}\\in S$ ， $\\underset{b}{\\rightarrow}\\in S$ ， $t\\in R$ ， $t\\underset{a}{\\rightarrow}+(1-t)\\underset{b}{\\rightarrow}\\in S$ 。则该点集为凸包。

闵可夫斯基

定义点集和的闵可夫斯基和 $P + Q$ 为 $P + Q=\\underset{a}{\\rightarrow}+\\underset{b}{\\rightarrow}|\\underset{a}{\\rightarrow}\\in P$ ， $\\underset{b}{\\rightarrow}\\in Q$ 。函数(序列) 也可以视作点集，对于两个函数 $f\\;g$ ，其闵可夫斯基和可以定义为 (f + g)(x) = min_k(f(k) + g(x-k)) 或 (f + g)(x) = max_k(f(k) + g(x - k)) ，取决于你怎么看待这个函数 (序列)。

由于凸包有良好的性质，所以我们一般只考虑凸包的闵可夫斯基和。若点集合 P, Q 为凸包，则其闵可夫斯基和 $P + Q$ 也是凸包。证明取 $e = a + c \\in P + Q,f = b + d \\in P + Q$ ，其中 $a, b \\in P,c, d \\in Q$ 。对于 $t \\in [0, 1]$ ： te + (1 - t)f = t(a + c) + (1 - t)(b + d) = (ta + (1 - t)b) + (tc + (1 - t)d) $\\in P + Q$