状态 dp

好久没做 状态dp 的问题了,经常用来将 NP 问题,变得小规模可解问题。确实是一个很经典的东西,最重要的是知道 $dp[i][j]$ 的意义,其次才是状态转移。

hdu 5691

这题大意:给你一些数,有些数固定有些数,另外的数可以随意调节,问你如何调解使得下式取值最大

$$ a_0 a_1 + a_1 a_2 + \cdots + a_{n-1} a_n $$

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

设 $i$ 的 2 进制表示是 $0 \cdots 0 i_1 0 \cdots 0 ix 0\cdots 0$ 有 $x$ 位。
$dp[i][j]$ 表示前 $x$ 个空 分别填了 $a[i_1],a[i_2],\cdots,a[i_x]$ 的一个排列 且 $i_x = j$ 使目标最大的最大值。
那么,自然地有
$$ dp[i|(1<<k][k] = max(dp[i][j]+a[j]*a[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
#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(){
// freopen("/Users/dna049/Desktop/AC/in","r",stdin);
// freopen("/Users/dna049/Desktop/AC/out","w",stdout);
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;
}