动态规划的优化

发表于 | 分类于 | 阅读次数:

##状态压缩
###[COGS217][USACO Open05] Disease Management

$N$ 头奶牛中共有 $D$ 种疾病，选择性地给一些奶牛挤奶，使得挤出牛奶中的疾病总数不超过 $K$ 种，求最多能给多少奶牛挤奶。

$1\leq N\leq100,1\leq D\leq15,1\leq K\leq D$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
using namespace std;

int N,D,K;

int f[1<<15+5];

int ill[1005];bool ok[1<<15+5];

int main()
{
	freopen("disease.in","r",stdin);
	freopen("disease.out","w",stdout);
	int i,j,x,y;scanf("%d%d%d",&N,&D,&K);
	for(i=1;i<=N;i++)
	{
		scanf("%d",&x);
		for(j=1;j<=x;j++)
		{
			scanf("%d",&y);
			ill[i]+=1<<(y-1);
		}
	}
	int tot=(1<<D)-1;
	for(i=0;i<=tot;i++)
	{
		int icnt=0;
		for(j=i;j;j>>=1)
			if(j&1) icnt++;
		if(icnt<=K) ok[i]=true;
	}
	for(i=1;i<=N;i++)
		for(j=tot;j>=0;j--)
			f[j|ill[i]]=max(f[j|ill[i]],f[j]+1);
	int ans=0;
	for(i=0;i<=tot;i++)
		if(ok[i]) ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}

##数位动规
###区间满足条件的整数个数
数位动规能解决一类形如求一个区间内满足条件的整数个数一类经典问题。

一般的做法是：记录 $f[i][j]$ 为首位为 $j$ 长度为 $i$ 的满足条件的数的个数，然后在之后的计算利用储存的值得到最终答案。

数位动规十分易懂且好写（所以说不经常出现），唯一的难点就在于前导零的处理，看三道题感受一下吧。

###[HDU2098]不要 62

给定一个数字范围 $[l,r]$ ，问满足不含有 $4$ 且不含有连续的两个数 $62$ 的数字的数量。

$r\leq10^6$

这道题处理前导零可以在初始化 DP 数组时允许有前导零，然后在计算答案时对每一位分别统计，对一位只统计其整的部分（其中就包括了位数少的情况，因为之前算进去了），零的部分放到后面计算。

这样的做法虽然简单，但适用范围十分狭窄。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstdio>
#include<cstring>

int f[10][10];

inline void initDp()
{
	int i,j,k;
	f[0][0]=1;
	for(i=1;i<=7;i++)
		for(j=0;j<=9;j++)
			for(k=0;k<=9;k++)
				if(j!=4&&!(j==6&&k==2))
					f[i][j]+=f[i-1][k];
}

int num[10];

int solve(int x)
{
	memset(num,0,sizeof(num));
	int res=0,len=0;
	while(x) num[++len]=x%10,n/=10;
	for(i=len;i>=1;i--)
	{
		for(j=0;j<num[i];j++)
			if(!(num[i+1]==6&&j=2))
				ans+=f[i][j];
		if(num[i]==4||(num[i+1]==6&&num[i]=2)) break;
	}
	return res;
}

int main()
{
	int i;
	int n,m;
	initDp();
	while(scanf("%d%d",&n,&m)&&n&&m)
		printf("%d\n",solve(m+1)-solve(n));
	return 0;
}

###[BZOJ1026][SCOI2009]windy数

给定一个区间 $[l,r]$ ，求满足相邻两个数字只差最小为 $2$ 的数的个数。

$r\leq2\times10^9$

由于这道题我们不能像
##斜率优化
###[BZOJ1010][HNOI2008] 玩具装箱toy
由题意，易得如下状态转移方程：

$$f[i]=min{f[j]+(sum[i]-sum[j]+i-j-1-L)^2} ,j<i$$

令 $g[i]=sum[i]+i,L=L+1$

则 $f[i]=min{f[j]+(g[i]-g[j]-L)^2}$

证明决策单调性

假设在状态 $i$ 处的 $k$ 决策优于 $j$ 决策，即

$f[k]+(g[i]-g[k]-L)^2\leq f[j]+(g[i]-g[j]-L)^2$

则对于 $i$ 后的所有状态 $t$ ，要证明决策单调性

即
$$
\begin{eqnarray}
f[k]+(g[t]-g[k]-L)^2&\leq&f[j]+(g[t]-g[j]-L)^2\
f[k]+(g[i]+v-g[k]-L)^2&\leq&f[j]+(g[i]+v-g[j]-L)^2\
f[k]+(g[i]-g[k]-L)^2+2v\cdot (g[i]-g[k]-c)+v^2&\leq&f[j]+(g[i]-g[j]-c)^2+2v\cdot (g[i]-g[j]-L)+v^2\
2v\cdot (g[i]-g[k]-c)&\leq&2v\cdot (g[i]-g[j]-L)\
\end{eqnarray}
$$
即证明 $g[k]\geq g[j]$ （显然）

证明完毕

那么接下来就要求斜率方程

$$
\begin{eqnarray}
f[k]+(g[i]-g[k]-L)^2&\leq&f[j]+(g[i]-g[j]-L)^2\
f[k]+g[i]^2-2\cdot g[i]\cdot (g[k]+L)+(g[k]+L)^2&\leq&f[j]+g[i]^2-2\cdot g[i]\cdot (g[j]+L)+(g[j]+L)^2\
f[k]-2\cdot g[i]\cdot (g[k]+L)+(g[k]+L)^2&\leq&f[j]-2\cdot g[i]\cdot (g[j]+L)+(g[j]+L)^2\
\frac{f[k]+(g[k]+L)^2-f[j]-(g[j]+L)^2}{2\cdot (g[k]-g[j])}&\leq&g[i]
\end{eqnarray}
$$

$g[i]$ 是单调递增的，我们使用队列维护一个下凸壳，每次取出队头作为决策

加入决策 $i$ 时，令队尾为 $q[r]$ ，前一个为 $q[r-1]$

满足 $slope(q[r],i)<slope(q[r-1],q[r])$ 时，显然队尾是无效的，将其弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**************************************************************
    Problem: 1010
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:176 ms
    Memory:2464 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
typedef long long ll;
const int MAXN=5e4+5;
 
ll n,L;
ll f[MAXN],g[MAXN],que[MAXN];
 
inline double calSlop(int j,int k)
{return (f[k]-f[j]+(g[k]+L)*(g[k]+L)-(g[j]+L)*(g[j]+L))/(2.0*(g[k]-g[j]));}
 
int main()
{
    int i,j;
    scanf("%lld%lld",&n,&L);L++;
    for(i=1;i<=n;i++) scanf("%lld",&g[i]);
    for(i=2;i<=n;i++) g[i]+=g[i-1];
    for(i=1;i<=n;i++) g[i]+=i;
    int hd,tl;
    hd=1,tl=0;que[++tl]=0;
    for(i=1;i<=n;i++)
    {
        while(hd<tl&&calSlop(que[hd],que[hd+1])<=g[i]) hd++;
        j=que[hd];
        f[i]=f[j]+(g[i]-g[j]-L)*(g[i]-g[j]-L);
        while(hd<tl&&calSlop(que[tl],i)<calSlop(que[tl-1],que[tl])) tl--;
        que[++tl]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

##矩阵快速幂优化
有时候我们会遇到一些状态转移方程是递推形式的动态规划问题，而数据范围很大时，我们使用朴素的递推方法会超时，这时我么你考虑用矩阵快速幂的方法将 $O(N)$ 的时间复杂度优化为 $O(log_2N)$
###[BZOJ1009][HNOI2008]GT考试

给出一个长度为 $M$ 的十进制数字串，求在一个长度为 $N$ 的十进制数字串中有多少种不出现长度为 $M$ 的那个串（对 $K$ 取模），两个串中均允许出现前导零。

$N\leq10^9,M\leq20,K\leq10^3$

这道题要是不看数据范围还感觉是数位动规，但 $N$ 能达到 $10^9$ 那就需要 $log$ 级别的优化了。

按顺序处理准考证号每一位，设 $f[i][j]$ 表示：准考证号前 $i$ 位中后j位与不吉利数的前j位相同时，前i位的方案数。

那么答案 $ans=f[n][0]+f[n][1]+…+f[n][m-1]$

$f[i][j]$ 的准确含义：

  • f[i][j]表示的每种方案不仅与其后j位有关，还应保证不含不吉利数
  • 为避免重复， $f[i][j]$ 表示的每种方案都不含长度大于j且与不吉利数的前缀相同的后缀（否则就会出现：从 $1$ 到 $m$ 标号，不吉利数为 $123124$ 时， $f[i][2]$ 计数的方案包含 $f[i][5]$ 计数的方案的情况）

状态转移：

$f[i][j]$ 只能由 $f[i-1][k]$ 得到，相当于填完第 $i-1$ 位后，将其后缀 $k$ (长为 $k$ 的后缀)后面新添一位 $num$ ，之后这个 $i$ 位数的与不吉利数前缀相同的最长后缀是：后缀 $j$

$i>0$ 时：
$f[i][j]=f[i-1][0]a[0][j]+f[i-1][1]a[1][j]+…+f[i-1][m-1]*a[m-1][j]$

比如：还是假设不吉利数为123124，那么 f[i][3]=f[i-1][2]+f[i-1][5]，因为 f[i-1][2]末尾的***12不能是12312，所以需要f[i-1][5]补充

但若不吉利数为123123，那么 f[i][3]=f[i-1][2]，因为 f[i][3]末尾的***123不能是123123

$i==0$ 时： $f[0][0]=1,f[0][others]=0$

其中， $a[k][j]$ 就表示上面提到的 $num$ 能取几个值，可以用 kmp算法 预处理出来，它是一个矩阵，这样就可以不重不漏地计数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**************************************************************
    Problem: 1009
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:1288 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
 
const int MAXL=25;
 
int N,M,P;
 
struct Mt{int m[MAXL][MAXL];Mt(){memset(m,0,sizeof(m));}};
Mt operator *(Mt a,Mt b)
{
    int i,j,k;
    Mt res;
    for(i=0;i<M;i++)
        for(j=0;j<M;j++)
            for(k=0;k<M;k++)
                res.m[i][j]=(res.m[i][j]+a.m[i][k]*b.m[k][j])%P;
    return res;
}
 
Mt qpow(Mt a,int n)
{
    int i;
    Mt res;
    for(i=0;i<M;i++) res.m[i][i]=1;
    for(i=1;i<=N;i<<=1,a=a*a)
        if(i&n) res=res*a;
    return res;
}
 
int next[MAXL];
char s[MAXL];
int main()
{
    int i,j;
    scanf("%d%d%d",&N,&M,&P);
    scanf("%s",s+1);
    for(i=2,j=0;i<=M;i++)
    {
        while(j&&s[j+1]!=s[i]) j=next[j];
        if(s[j+1]==s[i]) j++;
        next[i]=j;
    }
    Mt dp;
    for(i=0;i<M;i++)
        for(j=0;j<=9;j++)
        {
            int t=i;
            while(t&&s[t+1]-'0'!=j)
                t=next[t];
            if(s[t+1]-'0'==j) t++;
            if(t!=M) dp.m[t][i]=(dp.m[t][i]+1)%P;
        }
    Mt res=qpow(dp,N);
    int ans=0;
    for(i=0;i<M;i++) ans=(ans+res.m[i][0])%P;
    printf("%d\n",ans);
    return 0;
}