POJ.3709 K-Anonymous Sequence

1.Problem
3709 -- K-Anonymous Sequence (poj.org)

2.Idea
Deque

3.Source

 int n, k;  
 Int a[N];  
 Int dp[N], S[N];  
 int deq[N];  
 Int f(int j, int x)  
 {  
      return -a[j] * x + dp[j] - S[j] + a[j] * j;  
 }  
 bool check(int f1, int f2, int f3)  
 {  
      Int a1 = -a[f1], b1 = dp[f1] - S[f1] + a[f1] * f1;  
      Int a2 = -a[f2], b2 = dp[f2] - S[f2] + a[f2] * f2;  
      Int a3 = -a[f3], b3 = dp[f3] - S[f3] + a[f3] * f3;  
      return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);  
 }  
 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           scanf("%d%d", &n, &k);  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &a[i]);  
           }  
           for (int i = 0; i < n; i++) {  
                S[i + 1] = S[i] + a[i];  
           }  
           int s = 0, t = 1;  
           deq[0] = 0;  
           dp[0] = 0;  
           for (int i = k; i <= n; i++) {  
                if (i - k >= k) {  
                     while (s + 1 < t && check(deq[t - 2], deq[t - 1], i - k)) t--;  
                     deq[t++] = i - k;  
                }  
                while (s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) s++;  
                dp[i] = S[i] + f(deq[s], i);  
           }  
           printf("%lld\n", dp[n]);  
      }  
 }