POJ.3260 The Fewest Coins

1.Problem
3260 -- The Fewest Coins (poj.org)

2.Idea
Knapsack problem. Reference

3.Source

 #include <cstdio>  
 #include <cstring>  
 const int maxn = 101, maxt = 10001, maxv = 121, INF = 0x3f3f3f3f;  
 int n, t, lim, v[maxn], c[maxn], que[maxt + maxv * maxv][2], l, r, f[maxt + maxv * maxv], g[maxv * maxv], ans;  
 int main()  
 {  
      scanf("%d%d", &n, &t);  
      for(int i = 0; i < n; ++i)  
      {  
           scanf("%d", v + i);  
           if(lim < v[i])  
                lim = v[i];  
      }  
      for(int i = 0; i < n; ++i)  
           scanf("%d", c + i);  
      lim *= lim;  
      t += lim;  
      memset(f, 0x3f, sizeof f);  
      memset(g, 0x3f, sizeof g);  
      f[0] = g[0] = 0;  
      for(int i = 0; i < n; ++i)  
           for(int a = 0; a < v[i]; ++a)  
           {  
                l = r = 0;  
                for(int j = 0; j * v[i] + a <= t; ++j)  
                {  
                     int tmp = f[j * v[i] + a] - j;  
                     while(l < r && que[r - 1][1] >= tmp)  
                          --r;  
                     que[r][0] = j;  
                     que[r++][1] = tmp;  
                     f[j * v[i] + a] = que[l][1] + j;  
                     if(que[l][0] == j - c[i])  
                          ++l;  
                }  
           }  
      for(int i = 0; i < n; ++i)  
           for(int j = v[i]; j <= lim; ++j)  
                if(g[j] > g[j - v[i]] + 1)  
                     g[j] = g[j - v[i]] + 1;  
      t -= lim;  
      ans = INF;  
      for(int i = 0; i <= lim; ++i)  
           if(ans > f[t + i] + g[i])  
                ans = f[t + i] + g[i];  
      if(ans != INF)  
           printf("%d\n", ans);  
      else  
           puts("-1");  
      return 0;  
 }  

POJ.2823 Sliding Window

1.Problem
2823 -- Sliding Window (poj.org)

2.Idea
Using Deque

3.Source

 const int N = 1000006;  
 //////////////////////////////  
 int n, k;  
 int a[N];  
 int mn[N], mx[N];  
 int deq[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &k);  
      REP(i, n) scanf("%d", &a[i]);  
      //MIN values  
      int s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] >= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mn[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mn[i], i == n - k ? '\n' : ' ');  
      }  
      //MAX Values  
      s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] <= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mx[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mx[i], i == n - k ? '\n' : ' ');  
      }  
 }  

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]);  
      }  
 }