HDU 2829 Lawrence(四边形优化DP)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2829

题意：首先一条链上有n个数，两两之间相乘的结果求和为这条链的权值(n==1的话答案就是0)，然后可以进行最多m次操作，每次可以把一条链的某一条边剪断变成两条链，两条链的权值各自算，这样总的权值和会缩小。题目让你求m次操作后，最小的权值和为多少。

思路：经典的四边形优化的题目。

可以参考赵爽的《动态规划加速原理之四边形不等式》

简单的说，就是一点状态方程满足论文里面的两个条件的话，那么他们的决策存在单调性，即w(i, j)的决策k = f(i, j) f()函数满足 f(i-1, j) <= f(i, j) <= f(i,j+1)

然后我们可以利用上一次循环已经记录下来的f(i-1, j)和f(i,j+1)来限定f(i,j)的枚举范围使得本来需要O(n)枚举的复杂度降到O(1) (带常数吧?)

回归到这题，我们可以这样定义一个状态dp(i, j)代表前j个，i次操作后的最小值，f(i, j)记录最后一次操作的位置。

那么dp(i, j)的值可以由min{dp(i-1, k) + w(k+1, j)}得到,而k可以从f(i-1,j)枚举到j-1即可，并记录最优的下标作为f(i,j)的值。

这样可以做到总体复杂度为O(n^2)左右。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 typedef __int64 lld;
 7 const lld INF = 1LL<<60;
 8 const int MAXN = 1005;
 9 int arr[MAXN], n, m;
10 int sum[MAXN];
11 int F[MAXN][MAXN];
12 lld dp[MAXN][MAXN];
13 lld w[MAXN][MAXN];
14 
15 void init() {
16     memset(w, 0, sizeof(w));
17     sum[0] = 0;
18     for (int i = 1; i <= n; i++) {
19         sum[i] = sum[i-1] + arr[i];
20     }
21     for (int i = 1; i <= n; i++) {
22         for (int j = i + 1; j <= n; j++) {
23             w[i][j] = w[i][j-1] + arr[j] * (sum[j-1]-sum[i-1]);
24         }
25     }
26 }
27 
28 int main() {
29     while (scanf("%d%d", &n, &m) == 2) {
30         if (!n && !m) break;
31         for (int i = 1; i <= n; i++) {
32             scanf("%d", &arr[i]);
33         }
34         init();
35         for (int i = 1; i <= n; i++) {
36             dp[0][i] = w[1][i]; F[0][i] = 1;
37         }
38         for (int i = 1; i <= m; i++) {
39             for (int j = 1; j <= i; j++) dp[i][j] = 0;
40             for (int j = i + 1; j <= n; j++) {
41                 int ind = F[i-1][j];
42                 lld Min = INF;
43                 for (int k = F[i-1][j]; k < j; k++) {
44                     if (Min > dp[i-1][k] + w[k+1][j]) {
45                         Min = dp[i-1][k] + w[k+1][j];
46                         ind = k;
47                     }
48                 }
49                 F[i][j] = ind; dp[i][j] = Min;
50             }
51         }
52         printf("%I64d\n", dp[m][n]);
53     }
54     return 0;
55 }

View Code

PS:四边形不等式其实我并没有深透的理解，对于这道题目如何证明状态是满足四边形不等式的我也暂时不会，希望以后会了再来补齐吧。 :(

对于本题四边形定理成立的简单证明：

首先w(i, j)表示第i个到第j个构成一条独立的链所获得的值，

显然因为所有的值都是[1, 100]，所以w(i, j)满足区间包含的单调性，假如{ai, ai', aj, aj'}四个是连续的，

那么w(i, j) = ai*ai'+ai*aj+ai'*aj ; w(i', j') = ai'*aj + ai'*aj' + aj*aj' ; w(i, j') = ai*ai' + ai*aj + ai*aj' + ai'*aj + ai'*aj' + aj*aj' ; w(i', j) = ai' * aj

显然w(i, j) + w(i', j') <= w(i, j') + w(i', j)

所以这道题的状态是满足四边形不等式的。