动态规划初步

Update 2019.8.23

  • 又回来刷题了。。。。

  • 最近发现小绿本(《算法竞赛入门经典——习题与解答》)上的题值得一做,题解都写得很清真,不会像某谷上的题解,有一些奇技淫巧,不看 $Code$ 的情况下一般都可以打出来,提高自己的代码实现能力。
  • 然后我就先从动态规划开始吧 $qwq$ ~~

小紫书

例题:9-1

  • 题目链接:[洛谷] [UVA]

  • 分析:

    我觉得刘汝佳分析的思路写的很好,先抄下来:

    时间是单向流逝的,是一个天然的 ”序“ 。影响到决策的只有当前时间和所处车站,所以可以用 $d[i][j]$ 表示时刻 $i$ ,你在车站 $j$ ,最少还需要多少等待时间。边界条件是 $d[T][n] = 0$ ,其他 $d[T][j] = \infty (j \not= n)$ 。有 3 种决策:

    1. 等 1 分钟
    2. 做左边的车
    3. 做右边的车

    然后反着推就可以啦~

    思路好清晰鸭 qwq,我写题解完全不能达到的水平……

  • $Code$:

第一次打的时候用的是 $Emacs$ ,然后我的配置文件有一点问题,然后编译以后代码就被吃了。。。。

劳资又 tm 打了一遍。。。。

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
81
82
83
84
85
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXN = 1e3 + 5;
const int MAXT = 1e3 + 5;
const int INF = (1 << 30);

int n, m, t, dis[MAXN], f[MAXN][MAXT];

bool flag[MAXN][MAXT][2];

inline void Init () {
memset (dis, 0, sizeof (dis));
memset (flag, false, sizeof (flag));
memset (f, 0, sizeof (f));
return;
}

int main() {
int cnt = 0;

while (true) {
Init ();
cnt ++;

scanf ("%d", &n);
if (n == 0) {
break;
}

scanf ("%d", &t);
for (int i = 1; i <= n - 1; i++) {
scanf ("%d", &dis[i]);
}

scanf ("%d", &m);
for (int i = 1; i <= m; i++) {
int temp;
scanf ("%d", &temp);
for (int j = 1; j <= n; j++) {
flag[j][temp][0] = true;
temp += dis[j];
}
}

scanf ("%d", &m);
for (int i = 1; i <= m; i++) {
int temp;
scanf ("%d", &temp);
for (int j = n; j >= 1; j--) {
flag[j][temp][1] = true;
temp += dis[j - 1];
}
}

for (int i = 1; i <= n; i++) {
f[i][t] = INF;
}
f[n][t] = 0;

for (int i = t - 1; i >= 0; i--) {
for (int j = 1; j <= n; j++) {
f[j][i] = f[j][i + 1] + 1;

if(j < n && flag[j][i][0] && i + dis[j] <= t) {
f[j][i] = min (f[j][i], f[j + 1][i + dis[j]]);
}

if(j > 1 && flag[j][i][1] && i + dis[j - 1] <= t) {
f[j][i] = min (f[j][i], f[j - 1][i + dis[j - 1]]);
}
}
}

printf ("Case Number %d: ", cnt);
if (f[1][0] >= INF) {
printf ("impossible\n");
}
else printf ("%d\n", f[1][0]);
}
return 0;
}

小绿书—《习题与解答》

1.最长的滑雪路径

  • 题目链接:[洛谷]|[UVA(科学上网)]

  • 分析:直接引书中的话:

    用 $D[i,j]$ 来表示从 $[i,j]$ 开始能走的高度严格递减的最长路,则很容易发现 $D[i,j]$ 的状态转移方程:

    其中 $(i_1,j_1)$ 是比 [i,j] 高度小的 4 个相邻的格子之一。边界条件是当没有符合条件的 $i_1$ 和 $j_1$ 时, $D[i,j]=1$ 。使用记忆化搜索即可,时间复杂度 $O(R \times C)$ 。

    另外值得注意的是,记得不要让搜索越界!我是多久没写过搜索了,因为这个东西我调了 20 分钟 QAQ​

  • $Code$:

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXRC = 1e2 + 5 ;
const int cmp[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int T, r, c, ans ;
int data[MAXRC][MAXRC],dp[MAXRC][MAXRC];
char ch[MAXRC];
inline void Init(){
ans=0;
memset (data,0,sizeof (data));
memset (dp,0,sizeof (dp));
return;
}
void DP (int x,int y){
for (int i=0;i<4;i++){
int tox=x+cmp[i][0];
int toy=y+cmp[i][1];
if (tox<1||tox>r||toy<1||toy>c) continue;
if (data[tox][toy]<data[x][y]){
if (!dp[tox][toy]){
dp[tox][toy]=1;
DP(tox,toy);
}
dp[x][y]=max(dp[x][y],dp[tox][toy]+1);
}
}
ans=max(ans,dp[x][y]);
return;
}
int main() {
scanf ("%d" ,&T);
while (T--) {
scanf ("%s", ch);
printf ("%s: ", ch);
Init();
scanf ("%d%d", &r, &c);
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
scanf ("%d",&data[i][j]);
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
if (dp[i][j])
continue;
dp[i][j]=1;
DP(i,j);
}
}
printf ("%d\n",ans);
}
return 0;
}

2.免费糖果

  • 题目链接:[洛谷]|[UVA(科学上网)]
  • 分析:用 $dp[a,b,c,d]$ 来表示 4 个队列的拿取情况所对应口袋中的糖数。枚举每一种情况,如果篮子里有这种糖果了,就把篮子相应的糖果 $-1$ ;反之, $+1$ 。可以使用记忆化搜索实现,这样可以去除大量重复情况。
  • $Code$:
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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=45;
int data[5][MAXN],n;
int dp[MAXN][MAXN][MAXN][MAXN];
int top[5];
inline void Init(){
top[1]=top[2]=top[3]=top[4]=1;
memset(dp,-1,sizeof (dp));
return;
}
int dfs (int cnt,bool flag[]){
int ans=0;
int a=top[1];
int b=top[2];
int c=top[3];
int d=top[4];
if (dp[a][b][c][d]!=-1) return dp[a][b][c][d];
if (cnt==5) return dp[a][b][c][d]=0;
for (int i=1;i<=4;i++){
if (top[i]>n) continue;
int to=data[i][top[i]];
top[i]++;
if (flag[to]){
flag[to]=false;
ans=max(ans,dfs(cnt-1,flag)+1);
flag[to]=true;
}
else {
flag[to]=true;
ans=max(ans,dfs(cnt+1,flag));
flag[to]=false;
}
top[i]--;
}
dp[a][b][c][d]=ans;
return dp[a][b][c][d];
}
int main(){
while (true){
scanf ("%d",&n);
if (!n) return 0;
Init();
bool flag[MAXN];
memset(flag,false,sizeof (flag));
for (int i=1;i<=n;i++)
for (int j=1;j<=4;j++)
scanf ("%d",&data[j][i]);
printf ("%d\n",dfs(0,flag));
}
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×