HDU 3480 DP 斜率优化 Division

把n个数分成m段，每段的值为(MAX - MIN)²，求所能划分得到的最小值。

依然是先从小到大排个序，定义状态d(j, i)表示把前i个数划分成j段，所得到的最小值，则有状态转移方程：

d(j, i) = min { d(j-1, k) + (a_i - a_k+1)² | 0 ≤ k < i }

设 l < k < i，且由k转移得到的状态比由l转移得到的状态更优。

有不等式：

$d(j-1,l)+(a_i-a_{l+1})^2\geq d(j-1,k)+(a_i-a_{k+1})^2$

整理成斜率形式：

$\frac{\left[d(j-1,l)+{a_{l+1}}^2 \right ]-\left[d(j-1,k)+{a_{k+1}}^2 \right ]}{a_{l+1}-a_{k+1}}\leq 2a_i$

后面的就可以相当于套模板了，不过这里要用滚动数组优化一下空间。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int maxm =  + ;

 const int INF = 0x3f3f3f3f;

 int n, m;

 int a[maxn];

 int d[][maxn];

 int head, tail;

 int Q[maxn];

 int cur;

 int inline Y(int x) { return d[cur^][x] + a[x+] * a[x+]; }

 int inline DY(int p, int q) { return Y(q) - Y(p); }

 int inline DX(int p, int q) { return a[q+] - a[p+]; }

 int main()

 {

     freopen("in.txt", "r", stdin);

     int T; scanf("%d", &T);

     for(int kase = ; kase <= T; kase++)

     {

         scanf("%d%d", &n, &m);

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

         sort(a + , a +  + n);

         memset(d[], 0x3f, sizeof(d[]));

         d[][] = ;

         cur = ;

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

         {

             cur ^= ;

             head = tail = ;

             Q[tail++] = ;

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

             {

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

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

                 Q[tail++] = j;

                 d[cur][j] = d[cur^][Q[head]] + (a[j]-a[Q[head]+]) * (a[j]-a[Q[head]+]);

             }

         }

         printf("Case %d: %d\n", kase, d[cur][n]);

     }

     return ;

 }

代码君

下面是四边形不等式优化的代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int maxm =  + ;

 const int INF = 0x3f3f3f3f;

 int n, m;

 int a[maxn];

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

 int main()

 {

     int T; scanf("%d", &T);

     for(int kase = ; kase <= T; kase++)

     {

         scanf("%d%d", &n, &m);

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

         sort(a + , a +  + n);

         memset(s, , sizeof(s));

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

         {

             int j;

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

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

         }

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

         {

             s[][i] = ;

             d[][i] = (a[i] - a[]) * (a[i] - a[]);

         }

         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 t = d[i-][k] + (a[j] - a[k+]) * (a[j] - a[k+]);

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

                     {

                         d[i][j] = t;

                         s[i][j] = k;

                     }

                 }

             }

         }

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

     }

     return ;

 }

代码君

巴特西

HDU 3480 DP 斜率优化 Division

最新文章

热门文章