HDU 2829 斜率优化DP Lawrence

题意：n个数之间放m个障碍，分隔成m+1段。对于每段两两数相乘再求和，然后把这m+1个值加起来，让这个值最小。

设：

d(i, j)表示前i个数之间放j个炸弹能得到的最小值

sum(i)为前缀和，cost(i)为前i个数两两相乘之和。

则有状态转移方程： $d(i, j) = d(k, j-1) + cost_i - cost_k - sum_k (sum_i-sum_k)|0\leq k< i \}$

设0 ≤ l < k < i，且k比l更优，有不等式：

$d(l,j-1)+cost_i-cost_l-sum_l(sum_i-sum_l)\geq d(k,j-1)+cost_i-cost_k-sum_k(sum_i-sum_k)$

整理得到，注意不等号方向：

$\frac{\left [ d(l,j-1)-cost_l+{sum_l}^2 \right ] - \left [ d(k,j-1)-cost_k+{sum_k}^2 \right ]}{sum_l-sum_k}\leq sum_i$

最后变成了斜率的形式，下面就用一个队列维护即可。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, m;

 int sum[maxn], cost[maxn];

 int d[maxn][maxn];

 int head, tail;

 int Q[maxn];

 int j;

 int inline Y(int i)

 {

     return d[i][j-] + sum[i] * sum[i] - cost[i];

 }

 int inline DY(int x1, int x2) { return Y(x2) - Y(x1); }

 int inline DX(int x1, int x2) { return sum[x2] - sum[x1]; }

 int inline DP(int x1, int x2) { return d[x1][j-] + cost[x2] - cost[x1] - sum[x1]*(sum[x2]-sum[x1]); }

 int main()

 {

     while(scanf("%d%d", &n, &m) ==  && n)

     {

         for(int i = ; i <= n; i++) scanf("%d", sum + i);

         for(int i = ; i <= n; i++) sum[i] += sum[i - ];

         for(int i = ; i <= n; i++) cost[i] = cost[i-] + (sum[i]-sum[i-])*sum[i-];

         for(int i = ; i <= n; i++) d[i][] = cost[i];

         for(j = ; j <= m; j++)

         {

             head = tail = ;

             Q[tail++] = ;

             for(int i = ; i <= n; i++)

             {

                 while(head +  < tail && DY(Q[head], Q[head+]) <= sum[i] * DX(Q[head], Q[head+])) head++;

                 d[i][j] = DP(Q[head], i);

                 while(head +  < tail && DY(Q[tail-], i) * DX(Q[tail-], Q[tail-]) <= DY(Q[tail-], Q[tail-]) * DX(Q[tail-], i)) tail--;

                 Q[tail++] = i;

             }

         }

         printf("%d\n", d[n][m]);

     }

     return ;

 }

代码君

贴一个四边形不等式优化的代码对比一下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int n, m;

 int a[maxn], sum[maxn], cost[maxn];

 int d[maxn][maxn], s[maxn][maxn];

 int inline w(int k, int j)

 {

     return cost[j] - cost[k-] - sum[k-] * (sum[j] - sum[k-]);

 }

 int main()

 {

     while(scanf("%d%d", &n, &m) ==  && n)

     {

         m++;

         for(int i = ; i <= n; i++) scanf("%d", a + i);

         for(int i = ; i <= n; i++) sum[i] = sum[i - ] + a[i];

         for(int i = ; i <= n; i++) cost[i] = cost[i-] + sum[i-] *  a[i];

         memset(d, , sizeof(d));

         for(int i = ; i <= m; i++)

             for(int j = i + ; j <= n; j++) d[i][j] = INF;

         for(int i = ; i <= n; i++) { d[][i] = cost[i]; s[][i] = ; }

         for(int i = ; i <= m; i++)

         {

             s[i][n+] = n;

             for(int j = n; j >= i; j--)

             {

                 for(int k = s[i-][j]; k <= s[i][j+]; k++)

                 {

                     int tmp = d[i-][k] + w(k+, j);

                     if(tmp < d[i][j])

                         { d[i][j] = tmp; s[i][j] = k; }

                 }

             }

         }

         printf("%d\n", d[m][n]);

     }

     return ;

 }

代码君

巴特西

HDU 2829 斜率优化DP Lawrence

最新文章

热门文章