降维

有时候复杂度无法满足数据范围时,可以考虑寻找两个状态间的关系,只储存其中一个来表示两个状态,从而优化复杂度。

hdu5389

定义一个数的digital root为其各位之和得到一个数,然后再求这个数的各位之和,直到这个数只有一位。
题目要求满足n个数分为两部分,满足digital root 分别为A B的组数
很显然这是一个背包问题,我们很自然地得到转移方程
$$d_{i,dig(j+num_i),k} = \sum d{i-1,j,k}$$
$$d_{i,j,dig(k+num_i)} = \sum d{i-1,j,k}$$
$d_{i,j,k}$ 表示前i个数,选A的数digital root 为j,选B的数digit root 为k的方案数
然而这是一个$O(n^2)$的dp,无法适应题目的数据范围。

我们发现一个数的digital root,恰等于这个数%9(9的倍数的digital root记为0),那么对于每组方案必定满足$(A+B)\%9 = \sum num \%9$若不满足这个条件,则方案数为0(和题目要求有些出入)
所有现在我们保证了上述条件,那么很明显,我们分配好了一部分,另部分也随之确定
我们得到新的转移方程
$$d_{i,j} = \sum d_{i-1,j} \;\; 第i个数不加入A(加入B)$$
$$d_{i,(j+num_i)\%9} = \sum d_{i-1,j} \;\; 第i个数加入A$$
最后答案即$d_{n,A}$

CF316-E

统计(1,1)到(m,n)的回文子串数量,很巧妙的一个空间优化

我们联想一维的回文子串数量是怎么求的$d_{i,j}$表示i-j的回文子串数量
$$d_{i,j} = d_{i+1,j} + d_{i,j-1} + d_{i+1,j-1} \;,\; (if s_{i-1}=s_{j-1} \,,\, i<j-1)$$
我们令$d_{x_1,y_1,x_2,y_2}$ 表示从(x1,y1)到(x2,y2)的回文串数量,我们很容易写出记忆化搜索
我们发现x1+y1 = m+n-x2+y2,记忆化只需要记录x1,y1,x2,而y2可以由这三项确定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int dp(int x1,int y1,int x2,int y2)
{
if(x1>x2 || y1>y2) return 0;
if(pic[x1][y1] != pic[x2][y2]) return 0;
if(x1 == x2 || y1 == y2)
{
if(x1==x2)
{
if(y2 - y1<=2) return pic[x1][y1] == pic[x2][y2];
}
else
{
if(x2 - x1<=2) return pic[x1][y1] == pic[x2][y2];
}
}
int &ans = d[x1][y1][x2];
if(ans!=-1) return ans;
ans = 0;
ans = (ans+dp(x1+1,y1,x2-1,y2)) % mod;
ans = (ans+dp(x1,y1+1,x2-1,y2)) % mod;
ans = (ans+dp(x1+1,y1,x2,y2-1)) % mod;
ans = (ans+dp(x1,y1+1,x2,y2-1)) % mod;
return ans;
}

然而这样做会MLE,我们需要用时间换空间了。
我们定义$d_{i,x_1,x_2}$表示从横坐标x1到x2的方案数,其中i=x1+y1,为斜向划分的若干阶段,每一阶段都可以由i得出y1和y2,这样就可以用滚动数组存储了。
$$d_{i,x_1+1,x_2-1} += d_{i-1,x_1+1,x_2} + d_{i-1,x_1,x_2-1} + d_{i-1,x_1+1,x_2-1} + d_{i-1,x_1,x_2} $$

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
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int maxn = 510;
int d[2][maxn][maxn];
char pic[maxn][maxn];

inline void add(int &a,int b)
{
a += b;
if(a>=mod) a-=mod;
}

int main()
{
//freopen("test.txt","r",stdin);
int n,m;
while(scanf("%d %d",&n,&m)==2)
{
for(int i=0;i<n;++i) scanf("%s",pic[i]);
if(pic[0][0]!=pic[n-1][m-1])
{
puts("0");
continue;
}
memset(d,0,sizeof d);
int cur = 0;
d[cur][0][n-1] = 1;
int N = (m+n-2);
for(int t=1;t<=N/2;++t)
{
cur^=1;
memset(d[cur],0,sizeof d[cur]);
for(int i=0;i<=t;++i)
{
for(int k=n-t-1;k<n;++k)
{
// printf("(%d,%d) (%d,%d)\n",i,t-i,k,N-t-k);
if(i>k || t-i > N-t-k) continue;
if(pic[i][t-i]==pic[k][N-t-k])
{
add(d[cur][i][k],d[1-cur][i][k]);
if(i-1>=0) add(d[cur][i][k],d[1-cur][i-1][k]);
if(k+1<n) add(d[cur][i][k],d[1-cur][i][k+1]);
if(i-1>=0 && k+1<n) add(d[cur][i][k],d[1-cur][i-1][k+1]);
}
}
}
}
int ans = 0 , t=N/2;
if(N&1)
{
for(int i=0;i<=t;++i)
{
add(ans,d[cur][i][i+1]);
add(ans,d[cur][i][i]);
}
}
else
{
for(int i=0;i<=t;++i)
{
if(i-1>=0) add(ans,d[cur][i-1][i]);
add(ans,d[cur][i][i]);
if(i+1<n) add(ans,d[cur][i][i+1]);
if(i-1>=0 && i+1<n) add(ans,d[cur][i+1][i-1]);
}
}
printf("%d\n",ans);
}
return 0;
}

滚动数组

我们在进行转移的过程中,当前状态只与上一(几)阶段状态有关,我们可以用只保存上一(几)阶段的状态,然后滚动更新。
由于滚动数组的应用十分广泛,这里不再举例,背包dp双塔dp等专题中均有提到。

离散化

与一般的离散化思想一样,将无法表示的状态映射到可以表示的区间当中。
例子见下面 hdu5406

数据结构

单调队列

这个优化在背包dp中提过。

树状数组

当某一维状态呈递增/递减性质时,可以用数据结构快速找上一阶段的最优值

hdu5406

$d_{i_j}$ 表示第一个人所吃最后一个高度为i,第二个人所吃最后一个高度为j的最多数量。
$$ d_{i_j} = max(d_{i_k})+1 \;\; 1 \le k < j $$
然后i和j是对称的(可以相互转换),然后可以用树状数组$O(logn)$找到$max(d_{i_k})$
另外,这道题需要对高度离散化。

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
69
70
71
72
73
74
75
76
77
78
79
80
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 1010;

struct P
{
int x,y;
bool operator<(const P& rhs) const
{
return x>rhs.x || (x == rhs.x && y<rhs.y);
}
} save[maxn];

int p[maxn],pn,n,d[maxn][maxn];

void update(int& x,int y)
{
if(x<y) x = y;
}

void add(int x,int y,int v)
{
for(; y<=pn ;y += y&-y) update(d[x][y],v);
}

int get(int x,int y)
{
int res = 0;
for(;y ;y -= y&-y) update(res,d[x][y]);
return res;
}

int main()
{
//freopen("test.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
pn = 0;
for(int i=1;i<=n;++i)
{
scanf("%d %d",&save[i].x,&save[i].y);
p[pn++] = save[i].y;
}
sort(p,p+pn);
pn = unique(p,p+pn) - p;

for(int i=1;i<=n;++i)
{
save[i].y = lower_bound(p,p+pn,save[i].y) - p + 1; //离散化
}

sort(save+1,save+n+1);

int temp[maxn];

memset(d,0,sizeof d);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=pn;++j) temp[j] = get(j,save[i].y)+1;
for(int j=1;j<=pn;++j)
{
add(save[i].y,j,temp[j]);
add(j,save[i].y,temp[j]);
}
}

int ans = 0;
for(int i=1;i<=pn;++i) update(ans,get(i,pn));

printf("%d\n",ans);
}
return 0;
}