【HDOJ】3480 Division

斜率dp+滚动数组。
  1 /* 3480 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int maxn = 10005;
 44 const int maxm = 5005;
 45 int dp[2][maxn];
 46 int Q[maxn];
 47 int a[maxn];
 48 int n, m;
 49 
 50 void solve() {
 51     int l, r;
 52     int p = 0, q = 1;
 53     
 54     rep(i, 1, n+1)
 55         dp[p][i] = (a[i] - a[1]) * (a[i] - a[1]);
 56     
 57     rep(i, 2, m+1) {
 58         l = r = 0;
 59         Q[r++] = i-1;
 60         rep(j, i, n+1) {
 61             while (l+1 < r) {
 62                 int k1 = Q[l];
 63                 int k2 = Q[l+1];
 64                 int x1 = a[k1+1];
 65                 int x2 = a[k2+1];
 66                 int y1 = dp[p][k1] + x1 * x1;
 67                 int y2 = dp[p][k2] + x2 * x2;
 68                 if ((y2-y1)<=2*a[j]*(x2-x1))
 69                     ++l;
 70                 else
 71                     break;
 72             }
 73             int k = Q[l];
 74             int x = a[k+1];
 75             dp[q][j] = dp[p][k] + (a[j]-x)*(a[j]-x);
 76             while (l+1 < r) {
 77                 int k1 = j;
 78                 int k2 = Q[r-1];
 79                 int k3 = Q[r-2];
 80                 int x1 = a[k1+1];
 81                 int x2 = a[k2+1];
 82                 int x3 = a[k3+1];
 83                 int y1 = dp[p][k1] + x1 * x1;
 84                 int y2 = dp[p][k2] + x2 * x2;
 85                 int y3 = dp[p][k3] + x3 * x3;
 86                 if ((y3-y2)*(x2-x1) >= (y2-y1)*(x3-x2))
 87                     --r;
 88                 else
 89                     break;
 90             }
 91             Q[r++] = j;
 92             #ifndef ONLINE_JUDGE
 93                 printf("l = %d, r = %d
", l, r);
 94             #endif
 95         }
 96         q = p;
 97         p ^= 1;
 98     }
 99     
100     int ans = dp[p][n];
101     printf("%d
", ans);
102 }
103 
104 int main() {
105     ios::sync_with_stdio(false);
106     #ifndef ONLINE_JUDGE
107         freopen("data.in", "r", stdin);
108         freopen("data.out", "w", stdout);
109     #endif
110     
111     int t;
112     
113     scanf("%d", &t);
114     rep(tt, 1, t+1) {
115         scanf("%d %d", &n, &m);
116         rep(i, 1, n+1)
117             scanf("%d", &a[i]);
118         sort(a+1, a+1+n);
119         printf("Case %d: ", tt);
120         solve();
121     }
122     
123     #ifndef ONLINE_JUDGE
124         printf("time = %d.
", (int)clock());
125     #endif
126     
127     return 0;
128 }