动态规划

动态规划是研究一大类问题(特别是最值问题)的一种思路。从大二刚开始ICPC竞赛的时候第一次遇到,到大三学运筹学系统的了解,再到后来一直成为解决问题的一种思考方式。可以说动态规划真的是万金油的方法。

计算机领域(或者说博弈论)中的动态规划,就如同数学中的数学归纳法,一样重要。

运用动态规划的能力,就好比武侠小说中的内功,是随着时间慢慢累积的。

动态规划应用举例

  • 数列的递推关系
  • 背包问题
  • 图论中Floyd算法,Dijkstra算法
  • 流水线问题,旅行商问题
  • 其它杂类问题

动态规划原理

动态规划 (dynamic programming)于1950s被 Richard Bellman 发现。引用这里的话,动态规划本质就是:

  • 定义问题的状态(必须满足”无后效性”:这个就很玄学了)
  • 写出状态间的转移方程

从而递推(分治)的解决问题。

难点就在于定义问题的状态

很多时候一个变量的问题,我们需要强行加一个(甚至两个)变量来定义状态

然后给出状态转移方程,再做时间空间的优化。

动态规划举例(长期更新)

codeforces1354F

有$n$张牌,$i$ 号牌的数值是$a_i$,当$i$号牌放入桌上,之前在桌上的牌,每张数值增加$b_i$,桌上的牌可以销毁(每张牌最多销毁一次),但是桌上牌的数量不能超过$k$。 问使桌上牌数值总和最大的放法。其中数据满足

由于牌的编号于问题无关,所以不妨设$b_i$单调递增。

状态定义:$dp[i][j]$ 表示:场上前$j$张牌数(编号都不超过$i$)的桌面牌总和最大值(其实还要减去后$k-j$张牌的原始面值)。如果不减去就有后效性了!!!

状态转移:我们考虑第$i$ 张牌,

  • 如果将它最终留在桌面上,那么它一定是最后一张放在桌面上的,因为$b_i$ 单调递增。此时$dp[i][j] = dp[i-1][j-1]+(j-1)b[i] + a[i]$
  • 如果它没留在桌面,那么它一定会在后来第$k$张牌加过buff,$dp[i][j] = dp[i-1][j] + (k-1)b[i]$

所以

我们可以用 $isin[i][j]$ 来标记桌上第$j$张牌是否是$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
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<bits/stdc++.h>
using namespace std;
const int N = 102;
int dp[N][N];
bool isin[N][N],chose[N];
using node = tuple<int,int,int>;
node q[N];
void getans(int n,int k){
for(int i=1;i<=n;++i){
dp[i][0] = dp[i-1][0]+(k-1)*get<2>(q[i]);
for(int j = 1;j<i && j<=k;++j){
int x = dp[i-1][j]+(k-1)*get<2>(q[i]);
int y = dp[i-1][j-1]+(j-1)*get<2>(q[i])+get<1>(q[i]);
if(x>y){
dp[i][j] = x;
isin[i][j] = false;
}else{
dp[i][j] = y;
isin[i][j] = true;
}
}
if(i<=k){
dp[i][i] = dp[i-1][i-1]+(i-1)*get<2>(q[i])+get<1>(q[i]);
isin[i][i] = true;
}
}
for(int i=n,j=k;i;--i){
if(isin[i][j]){
chose[i]=true;
--j;
}else{
chose[i]=false;
}
}
}

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
int cas,n,k,a,b;
cin>>cas;
while(cas--){
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a>>b;
q[i] = {i,a,b};

}
sort(q+1,q+n+1,[](const node & x, const node & y){
return get<2>(x)<get<2>(y);
});
cout<<(2*n-k)<<endl;
getans(n,k);
int last = 0;
for(int i=1;i<=n;++i){
if(chose[i]){
if(++last == k){
last = i;
break;
}
cout<<get<0>(q[i])<<" ";
}
}
for(int i=1;i<=n;++i){
if(!chose[i]) cout<<get<0>(q[i])<<" "<<-get<0>(q[i])<<" ";
}
cout<<get<0>(q[last])<<endl;
}
return 0;
}

hdu 5691

这题大意:给你一些数,数值固定,部分数的位置随意调节,问你如何调解使得下式取值最大

这确实是经典的状态转移问题:

设 $i$ 的 2 进制表示是 $0 \cdots 0 i_1 0 \cdots 0 i_x 0\cdots 0$ 有 $x$ 位。
$dp[i][j]$ 表示前 $x$ 个空 分别填了 $a[i_1],a[i_2],\cdots,a[i_x]$ 的一个排列 且 $i_x = j$ 使目标最大的最大值。
那么,自然地有

详细转移见代码:

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
#include <cstdio>
template<typename T>
void upmax(T &a,T b){ if (a<b) a=b;}
const int INF = 0x3f3f3f3f;
const int N = 16;
int a[N],p[N];
int dp[1<<N][N];
int main(){
int T, Case = 0;
scanf("%d",&T);
while(T--){
printf("Case #%d:\n",++Case);
int n, x;
scanf("%d",&n);
for(int i=0;i<n;++i) p[i] = -1;
for(int i=0;i<n;++i){
scanf("%d%d",a+i, &x);
if(x != -1) p[x] = i;
}
for(int i=0;i<(1<<n);++i){
for(int j=0;j<n;++j){
dp[i][j] = -INF;
}
}
if(p[0]!=-1) dp[1<<p[0]][p[0]] = 0;
else for(int i=0;i<n;++i) dp[1<<i][i] = 0;
for(int i=1;i<(1<<n);++i){
for(int j=0;j<n;++j){
if(!(i&(1<<j))) continue;
for(int k=0;k<n;++k){
if(i&(1<<k)) continue;
int x = __builtin_popcount(i);
if(p[x] == -1 || p[x] == k){
upmax(dp[i|(1<<k)][k], dp[i][j]+a[j]*a[k]);
}
}
}
}
int res = -INF;
for(int i=0;i<n;++i) upmax(res, dp[(1<<n)-1][i]);
printf("%d\n",res);
}
return 0;
}
欧尼酱,人家想喝可乐!