HDU 3045 DP 斜率优化 Picnic Cows

题意：将n个数分成若干组，每组数字的个数不少于t个，要把每组的数字减小到这组最小值，求所有数字减少的最小值。

先将这n个数从小到大排个序，可以想到一组里面的数一定是排序后相邻的。

设d(i)表示前i个数分完组以后减少的最小值，考虑j~i为一组，则有状态转移方程

$d(i)=min\{d(j-1) + sum_i - sum_{j-1} - a_i(i-j+1)|1\leq j\leq i-t+1\}$

还是一样的处理方法，设k < j ≤ i - t，且j~i为一组的值比k~i为一组的值更优。

则有不等式：

$d(k-1)+sum_i-sum_{k-1}-a_k(i-k+1)\geq d(j-1)+sum_i-sum_{j-1}-a_k(i-j+1)$

化简，把i分离出来，整理成斜率的形式：

$\frac{\left [ d(k-1) - sum_{k-1}-a_k(i-k+1) \right ] - \left [ d(j-1) - sum_{j-1}-a_k(i-j+1) \right ]}{a_k-a_j}\leq i$

写到这里就应该很清楚地能够看出来X和Y的表达式了。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int maxn =  + ;

 int n, t;

 LL a[maxn], sum[maxn];

 LL d[maxn];

 int head, tail;

 int Q[maxn];

 LL inline Y(int x) { return d[x-] - sum[x-] + a[x] * (x - ); }

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

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

 int main()

 {

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

     {

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

         sort(a + , a +  + n);

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

         memset(d, , sizeof(d));

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

         head = tail = ;

         Q[tail++] = ;

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

         {

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

             Q[tail++] = i - t + ;

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

             d[i] = d[Q[head]-] + sum[i] - sum[Q[head]-] - (i-Q[head]+) * a[Q[head]];

         }

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

     }

     return ;

 }

代码君

巴特西

HDU 3045 DP 斜率优化 Picnic Cows

最新文章

热门文章