【全程NOIP计划】动态规划及优化1

LIS

非常经典，最长上升子序列

设计状态

以f[x]f[x]表示序列a中以axa_x结尾的LIS长度

涉及转移

f[x]=maxi<x,ai≤ax(f[i]+1)f[x]=max_{i<x,a_i\le a_x}(f[i]+1)

DP的状态和转移

一个问题可以DP，是因为这个问题可以从小问题的解推出大问题的解

我们可以从初始状态的解，推出最终状态的解，从而解决问题

本质

首先我们把LIS的问题中的每个状态作为点，放在图上

我们知道f[1]=1f[1]=1，因为单个字符的LIS长度只有1，现在想知道f[4]f[4]，这就需要转移来实现

如果状态x可以直接抵达y状态，我们就连上x→yx \rightarrow y的有向边

如果我们按照上面的方式画图，我们就可以发现几个性质

1.DP的每一个状态对应着一个点

2.每种可能的转移方式，都对应着一条有向边

3.DP的求解顺序，等同于这张图的拓扑排序

4.必须是有向无环图DAG，否则无法找到合适的求解顺序

两种转移方式

DP有两种转移方法：

1.pull型，主要考察一个状态如何从其他状态推出结果

2.push型，主要考察一个状态得到解之后，如何去更新其他的状态

本质上对应着自顶向下的拓扑排序和自下向顶的拓扑排序

计数类DP实质上不是DP，但是和DP很像，所以我们也叫它DP

P1002 过河卒

思路

f[x][y]f[x][y]表示抵达(x,y)(x,y)的方案数量

可以很快找到转移
f[x][y]={0,marked[x][y]f[x][y−1]+f[x−1][y],otherwise f[x][y]=\begin{cases}0, &\text{marked[x][y]} \\ f[x][y-1]+f[x-1][y],&\text{otherwise} \end{cases}
然后加上滚动数组可以找到转移
f[x][y]={0,marked[x][y]f[x]+f[x−1],otherwise f[x][y]=\begin{cases}0, &\text{marked[x][y]} \\ f[x]+f[x-1],&\text{otherwise} \end{cases}

注意循环的顺序，如果我们从小到大枚举xx，则本层的xx会更新本层的x+1x+1，本层的x+1x+1会更新本层的$x+2 \dots $，事实上本层的值应该由上一层来确定

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int fx[]={0,-2,-1,1,2,2,1,-1,-2};
int fy[]={0,1,2,2,1,-1,-2,-2,-1};
int bx,by,mx,my;
long long f[30][30];
bool s[30][30];
int main()
{
	cin>>bx>>by>>mx>>my;
	bx+=1,by+=1,mx+=1,my+=1;
	f[1][1]=1;
	s[mx][my]=1;
	for(int i=1;i<=8;i++)
		s[mx+fx[i]][my+fy[i]]=1;
	for(int i=1;i<=bx;i++)
	{
		for(int j=1;j<=by;j++)
		{
			if(s[i][j]) continue;
			f[i][j]=max(f[i][j],f[i-1][j]+f[i][j-1]);
		}
	}
	cout<<f[bx][by]<<endl;
	return 0;
}
滚动数组技巧

一个DP可以通过滚动数组来优化，当且仅当其状态图是分层的，下k层的结果由上d层的结果唯一确定

单层滚动数组的通用写法

开两个数组arroldarr_{old},arrnewarr_{new}，分别保存旧层和新层，通过旧层计算出新层的值，然后覆盖掉旧层

覆盖可以通过memcpy或者交换指针实现。

通用写法的优势：无需考虑特殊的求值顺序

关于记忆化搜索

只需要直接实现pull型转移，无需在代码中考虑循环顺序

只经历可能达到的状态，不会经过无效的区间状态，节省时间

所以我们很多时候是喜欢记忆化搜索的，尤其是区间DP问题

写法上，我们判断是否记忆可以采用vis数组，如果DP结果可能是0，一定要把初值设为其他值

DAG最短路

题目

有一个DAG，给定一个S，和一个T，求S到T之间的最短距离

思路

用f(x)f(x)表示从起点到x的距离

那么显然有

f[x]=min(f[u]+dis[u][x])f[x]=min(f[u]+dis[u][x])

那我们能不能推广到任意图的最短路呢?

显然不行，因为如果有环的话会出现一个循环依赖问题

主要是因为产生了后效性

所以换一种设计状态方法：

设f[k][x]f[k][x]为从起点开始，经历不超过k个点，到达x的最短路径长度

我们一举解决了循环依赖问题，f[k][x]f[k][x]只会依赖于f[k−1][.]f[k-1][.]

状态转移如下

f[k][x]=min(f[k−1][u]+dis[u][x])f[k][x]=min(f[k-1][u]+dis[u][x])

注意到这个是分层的，滚动数组优化之后，就是Bellman−FordBellman-Ford单源最短路算法

用DP看Floyd

我们刚刚解决了单源最短路径问题，现在要求出图中任意两点间的距离，那我们如何DP呢？

第一时间想到f[u][v]f[u][v]表示u到v的距离，但由于循环依赖问题，没有合适的转移

于是考虑记录f[k][u][v]f[k][u][v]表示从u开始经历不超过k个点到达v的最短路

显然有f[k][u][v]=min(f[k−1][u][x]+dis[x][v])f[k][u][v]=min(f[k-1][u][x]+dis[x][v])

因为是分层的，滚动数组滚掉第一维，我们就可以得到了FloydFloyd算法

P1018 乘积最大

思路

用f[pos][d]f[pos][d]表示把数字串的[0,pos)[0,pos)位划分为dd段，得到的收益。则转移是显然的
f[pos][d]=maxx<pos(f[x][d−1]∗a[x,pos)) f[pos][d]=max_{x<pos}(f[x][d-1]*a_{[x,pos)})
技巧：

1.处理序列问题的时候，往往考虑将此序列的前缀作为子问题

2.处理字符串的时候采用左闭右开区间，常常可以省代码

没加高精度60分，高精度不想写来着

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int maxn=55;
int n,k;
int v[maxn];
char s[maxn];
int a[maxn][maxn];
int f[maxn][maxn];
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		v[i]=c-'0';
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		a[i][j]=(a[i][j-1]*10+v[j]);
	}
	for(int i=1;i<=n;i++)
	f[i][0]=a[1][i];
	for(int pos=1;pos<=n;pos++)
	{
		for(int d=1;d<=k;d++)
		{
			for(int x=1;x<pos;x++)
			f[pos][d]=max(f[pos][d],f[x][d-1]*a[x+1][pos]);
		}
	}
	cout<<f[n][k]<<'\n';
	return 0;
}

CF1061C Multiplicity

题目

从序列 {a1, a2, .. , an}\{a_1,\ a_2,\ ..\ ,\ a_n\} 中选出非空子序列 {b1, b2, .. , bk}\{b_1,\ b_2,\ ..\ ,\ b_k\}，一个子序列合法需要满足 ∀ i∈[1, k], i ∣ bi\forall\ i \in [1,\ k],\ i\ |\ b_i。求有多少互不相等的合法子序列，答案对 109+710^9 + 7 取模。

序列 {1, 1}\{1,\ 1\} 有 22 种选法得到子序列 {1}\{1\}，但 11 的来源不同，认为这两个子序列不相等。

思路

f[x][k]f[x][k]表示从序列的前x位选k个的方案数

f[x][k]f[x][k]从哪里来？

第x位要不要选做子序列的第k个？

则有f[x−1][k]f[x-1][k]和,f[x−1][k−1]f[x-1][k-1]中转移过来

那么我们就有
f[x][y]={f[x−1][y]+f[x−1][y−1],y∣a[i]f[x−1][y]otherwise f[x][y]= \begin{cases} f[x-1][y]+f[x-1][y-1],&y|a[i] \\ f[x-1][y] &otherwise \end{cases}
发现xx由x−1x-1唯一确定

可以加一个滚动数组优化

于是代码框架是：外层枚举x，内层枚举y进行转移

现在来优化时间，考虑内层循环的次数，我们知道，只有当y∣a[x]y|a[x]的那些y才需要特殊考虑，于是因数分解a[x]a[x]

总的复杂度O(nn)O(n\sqrt{n})

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int mod=1e9+7;
const int maxn=100005;
int n;
int a[maxn];
int f[maxn];
vector <int> fac;
void get_factor(int x)
{
	for(int i=1;i*i<=x;i++)
	{
		if(x%i==0)
		{
			fac.push_back(i);
			if(x!=i*i)
			fac.push_back(x/i);
		}
	}
	sort(fac.begin(),fac.end(),greater<int>());
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		get_factor(a[i]);
		for(auto j:fac)
		{
			if(j<=i)
			f[j]=(f[j]+f[j-1])%mod;
		}
		fac.clear();
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	ans=(ans+f[i])%mod;
	cout<<ans<<'\n';
	return 0;
}

P1004 方格取数

思路

两个人同时走和先后走是一样的结果，只要保证每个数只被取到一次

设计f[step][a][b][x][y]f[step][a][b][x][y]表示两个人各走stepstep步，第一个人走到(a,b)(a,b)，第二个人走到(x,y)(x,y)能获取的最大价值

有
f[step][a][b][x][y]=benifit+max{f[step−1][a−1][b][x−1][y]f[step−1][a−1][b][x][y−1]f[step−1][a][b−1][x−1][y]f[step−1][a][b−1][x][y−1] f[step][a][b][x][y]=benifit+max \begin{cases} f[step-1][a-1][b][x-1][y] \\ f[step-1][a-1][b][x][y-1] \\ f[step-1][a][b-1][x-1][y] \\ f[step-1][a][b-1][x][y-1] \\ \end{cases}

然后发现根据滚动数组，可以stepstep这一层滚掉，不难写出代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int N=15;
int n;
int w[N][N];
int f[N*2][N][N];
int main()
{
	memset(w,0,sizeof(w));
	cin>>n;
	while(1)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(x==0&&y==0&&z==0)
		break;
		w[x][y]=z;
	}
	memset(f,0,sizeof(f));
	for(int k=2;k<=n+n;k++)
	{
		for(int x1=max(1,k-n);x1<=min(k-1,n);x1++)
		{
			for(int x2=max(1,k-n);x2<=min(k-1,n);x2++)
			{
				int t=w[x1][k-x1];
				if(x1!=x2) t+=w[x2][k-x2];
				for(int a=0;a<=1;a++)
				{
					for(int b=0;b<=1;b++)
					f[k][x1][x2]=max(f[k][x1][x2],f[k-1][x1-a][x2-b]+t);
				}
			}
		}
	}
	cout<<f[2*n][n][n]<<endl;
	return 0; 
}

CF245H Queries for Number of Palindromes

思路

题意就是要统计l到r内的回文子串的个数

设答案为f[l][r]f[l][r],根据容斥原理
f[l][r]=f[l][r−1]+f[l+1][r]−f[l+1][r−1]+ispal(sl…r) f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1]+ispal(s_{l\dots r})
其中is_pal可以O(∣s∣2)O(|s|^2)预处理

所以整个问题可以在O(∣s∣2)O(|s|^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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int maxn=5005;
char s[maxn];
bool is_pal[maxn][maxn];
bool visit_pal[maxn][maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void get_is_pal(int l,int r)
{
    if(visit_pal[l][r])
    return;
    if(l==r||r==l+1)
	{
        is_pal[l][r]=(s[l]==s[r]);
        return;
    }
    get_is_pal(l+1,r-1);
    if(is_pal[l+1][r-1])
    is_pal[l][r]=(s[l]==s[r]);
    visit_pal[l][r]=true;
}
int f[maxn][maxn];
bool visit_dp[maxn][maxn];
void get_dp(int l,int r) 
{
    if(visit_dp[l][r])
    return;
    if(l==r)
	{
        f[l][r]=1;
        return;
    }
    if(r==l+1)
	{
        f[l][r]=2+is_pal[l][r];
        return;
	}
    get_dp(l,r-1);
    get_dp(l+1,r);
    get_dp(l+1,r-1);
    f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1]+is_pal[l][r];
    visit_dp[l][r]=true;
}
int main()
{
	scanf("%s",s+1);
    int len=strlen(s+1);
    for(int x=1;x<=len;x++)
        for(int y=x;y<=len;y++)
            get_is_pal(x,y);
    for(int x=1;x<=len;x++)
        for(int y=x;y<=len;y++)
            get_dp(x,y);
    int T=read();
    while(T--)
    {
    	cout<<f[read()][read()]<<'\n';
	}
    return 0;
}

P1385 密令

思路

首先发现一条性质：我们设字符串的总和为sum，则任何字母总和为sum的等长的串都是可以达到的。

证明：

采用构造方法，我们从前往后构造新的字符串，考虑第一个字符，如果比目标大就用(−1,+1)(-1,+1)变换，比目标小就用(+1,−1)(+1,-1)变换，然后去搞第二个字符……一次类推，直到搞完前n−1n-1位

至于最后一位，我们断言它此时必定等于目标串的最后一位，这是因为两种变换均不会改变字母和sumsum

于是整个问题就简化为：

给定sumsum，有多少种长度为nn的序列满足：

1.每个元素在[1,26][1,26]之间

2.序列和为sumsum

然后就开始DP，设f[k][x]f[k][x]表示长度为kk的序列之和为xx的方案数量，答案显然是f[n][sum]f[n][sum],然后转移就是显然的
f[k][x]=∑1≤i≤min(26,x)f[k−1][x−i] f[k][x]=\sum_{1 \le i \le min(26,x)}f[k-1][x-i]
注意最后要减去原先的那一个

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int mod=1e9+7;
int T;
char s[105];
int f[105][5005];
signed main()
{
	cin>>T;
	for(int i=0;i<26;i++)
	f[1][i]=1;
	for(int i=1;i<=100;i++)
	f[i][0]=1;
	for(int k=2;k<=100;k++)
	{
		for(int x=1;x<=2500;x++)
		{
			for(int i=0;i<26;i++)
			{
				if(x-i>=0)
				f[k][x]=(f[k][x]%mod+f[k-1][x-i]%mod)%mod;
			}
		}
	}
	while(T--)
	{
		scanf("%s",s+1);
		int tot=0;
		int len=strlen(s+1);
		for(int i=1;i<=len;i++)
		tot+=(int)(s[i]-'a');
		cout<<f[len][tot]%mod-1<<'\n';//要减去最开始的那一个！！ 
	}
	return 0;
}

CF106C Buns

设f[k][r]f[k][r]表示只做前k种包子，使用了r克面团，获得的收益

实际上类似于一个背包

考虑某种包子做ii个，则有状态转移方程
∀k,r,f[k][r]=max(f[k][r],f[k−1][r−i∗c[k]]+i∗d[k]) \forall k,r ,f[k][r]=max(f[k][r],f[k-1][r-i*c[k]]+i*d[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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1005;
int n,m;
int a[maxn],b[maxn],c[maxn],d[maxn];
int c0,d0;
int f[15][maxn];
int ans;
int main()
{
	cin>>n>>m>>c0>>d0;
	for(int i=1;i<=m;i++)
	cin>>a[i]>>b[i]>>c[i]>>d[i];
	//整挺好，就一个类似于背包的动态规划 
	for(int k=1;k<=m;k++)
    for(int r=0;r<=n;r++)
    for(int i=0;i*b[k]<=a[k]&&i*c[k]<=r;i++)
    f[k][r]=max(f[k][r],f[k-1][r-i*c[k]]+i*d[k]);
    for(int r=0; r<=n; r++)
    ans=max(ans,f[m][r]+(n-r)/c0*d0);
    cout<<ans<<'\n';
    return 0;
}