LHRG 李的博客

LHRG's blog

发表于 更新于 分类于 ， 本文字数： 2.2k 阅读时长 ≈ 8 分钟

\(\qquad\!\!\)除了基础动态规划中的三种动态规划以外，还有一些比较难的动态规划：

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 2.3k 阅读时长 ≈ 8 分钟
  • 1、线性dp：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)给定一个数列，求其中最长上升子序列的长度：

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
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n;
int a[N],f[N];
int ans; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	for(re int i=1;i<=n;i++)
	{
		for(re int j=0;j<i;j++)
		{
			if(a[i]>a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
		ans=max(ans,f[i]);
	}
	qwrite(ans);
	putchar('\n');
	return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 745 阅读时长 ≈ 3 分钟

\(\qquad\!\!\)在解决 dp 问题时，主要要从两点思考：

  • 1、状态：

\(\qquad\!\!\)通常来讲，状态的设立因题而异，大多数与答案的意义相同（dp数组 中的某个值即为答案）或者与答案具有直接联系（比如再经过某种统计即可得到答案）。

\(\qquad\!\!\)对于很难一眼看出状态（比如答案无法转移）的题，我们就要利用 dp的本质：“把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。”和 dp 最重要的一个性质：“无后效性”去推理。

\(\qquad\!\!\)根据无后效性，我们可以假设在这个阶段之前的阶段（注意，这个“之前”表示的是 dp转移 上的之前，可能是空间上的之前、数位上的之前、拓扑序上的之前……）都已经进行了最优化的决策。根据 dp的本质，如果之前的阶段的最优决策映射出的一种“结果”能以 某种方式 转移到此阶段的这种“结果”，且此时的这种“结果”也恰好为此时的最优化决策的这种映射，那么这种“结果”即为 dp的状态。

  • 2、转移方程：

\(\qquad\!\!\)通常来讲，转移方程的确立也是因题而异的，不过在得出了正确的状态之后，转移方程的确立方式一般比较显然。

\(\qquad\!\!\)前文中加粗的的“某种方式”，即可理解为一种状态到状态的转移方式。我们在将其具体化以后，即可得到对于相邻状态的转移方程。同时，对于很多题目的转移方程可以利用数学的计算或者数据结构的辅助得以在复杂度上得以化简，即为 dp的优化。

  • 3、实现方法：

\(\qquad\!\!\)一般来说，动态规划可以通过递推和记忆化搜索两种方式实现。

阅读全文 »

发表于 更新于 分类于 ， 本文字数： 3.2k 阅读时长 ≈ 12 分钟
  • 1、递推：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)共有 \(n\) 级台阶，每次可以上 \(1-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
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n,k;
int f[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
int main()
{
	n=qread();
	k=qread();
	f[0]=1;
	for(re int i=1;i<=n;i++)
	{
		for(re int j=max(0,i-k);j<i;j++)
		{
			f[i]+=f[j];
		}
	}
	qwrite(f[n]);
	putchar('\n');
    return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 本文字数： 597 阅读时长 ≈ 2 分钟
  • 1、起手式：
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
#include<bits/stdc++.h>
#define in inline
#define re register
using namespace std; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
int main()
{
	
	return 0;
}
阅读全文 »
0%