POJ.2010 Moo University - Financial Aid

1.Problem
http://poj.org/problem?id=2010

2.Idea
Preprocessing with priority_queue, and check every possible median values.

3.Source

 struct Cow {  
      int csat;  
      ll faid;  
      bool operator < (const Cow &a)const {  
           //if(csat == a.csat) return faid > a.faid; else   
           return csat < a.csat;  
      }  
 } Cows[100005];  
 ll d[100005], u[100005];  
 int c, n, k;  
 ll f;  
 void preProc(ll *l)  
 {  
      ll sum = 0LL;  
      priority_queue<int> q;  
      for (int i = 0; i < c; i++) {  
           if (i < k) {  
                l[i] = 13131313131313131;  
                q.push(Cows[i].faid);  
                sum += Cows[i].faid;  
           }  
           else {  
                l[i] = sum;  
                if (q.top() > Cows[i].faid) {  
                     sum += (Cows[i].faid - q.top());  
                     q.pop();   
                     q.push(Cows[i].faid);  
                }  
           }  
      }  
 }  
 int main()  
 {  
      cin >> n >> c >> f;  
      for (int i = 0; i < c; i++) {  
           cin >> Cows[i].csat >> Cows[i].faid;  
      }  
      k = n / 2;  
      sort(Cows, Cows + c);  
      preProc(d);  
      reverse(Cows, Cows + c);  
      preProc(u);  
      reverse(u, u + c);  
      reverse(Cows, Cows + c);  
      int ans = -1;  
      for (int i = 0; i < c; i++) {  
           if (d[i] + u[i] + Cows[i].faid <= f) {  
                ans = Cows[i].csat;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3614 Sunscreen

1.Problem
http://poj.org/problem?id=3614

2.Idea
Greedy method works. Process from the cow that has the min of maxSPF.

3.Source

 int c, l;  
 int Lot[1003];  
 struct Cow {  
      int l, r;  
      bool operator < (const Cow &a)const {  
           return r < a.r;  
      }  
 } Cows[2503];  
 int main()  
 {  
      cin >> c >> l;  
      for (int i = 0; i < c; i++) {  
           cin >> Cows[i].l >> Cows[i].r;  
      }  
      sort(Cows, Cows + c);  
      for (int i = 0; i < l; i++) {  
           int x, y;  
           cin >> x >> y;  
           Lot[x] += y;  
      }  
      int ans = 0;  
      for (int i = 0; i < c; i++) {  
           for (int j = Cows[i].l; j <= Cows[i].r; j++) {  
                if (Lot[j] > 0) {  
                     ans++;  
                     Lot[j]--;  
                     break;  
                }  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1793 Find them, Catch them

1.Problem
http://poj.org/problem?id=1703

2.Idea
Using Union-Find set.

3.Source

 int Parent[200005];  
 int Size[200005];  
 int n, m;  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n >> m;  
           for (int i = 1; i <= 2 * n; i++) make_set(i);  
           char c;  
           int a, b;  
           for (int i = 0; i < m; i++) {  
                scanf(" %c %d %d", &c, &a, &b);  
                //cin >> c >> a >> b;  
                if (c == 'D') {  
                     union_sets(a, b + n);  
                     union_sets(b, a + n);  
                }  
                else {  
                     if (find_set(a) == find_set(b) || find_set(a + n) == find_set(b + n)) {  
                          puts("In the same gang.");  
                     }  
                     else if (find_set(a) == find_set(b + n) || find_set(a + n) == find_set(b)) {  
                          puts("In different gangs.");  
                     }  
                     else {  
                          puts("Not sure yet.");  
                     }  
                }  
           }  
      }  
      return 0;  
 }  

POJ.2236 Wireless Network

1.Problem
http://poj.org/problem?id=2236

2.Idea
Using Disjoint set/Union-find set

3.Source

 double x[1003], y[1003];  
 int n;  
 double d;  
 bool g[1003][1003];  
 bool on[1003];  
 int Parent[1004];  
 int Size[1004];  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 double dist(double x1, double x2, double y1, double y2)  
 {  
      return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));  
 }  
 int main()  
 {  
      cin >> n >> d;  
      for (int i = 0; i < n; i++) {  
           cin >> x[i] >> y[i];  
           make_set(i);  
      }  
      for(int i=0;i<n;i++)  
           for (int j = 0; j < n; j++) {  
                if (dist(x[i] , x[j] , y[i] , y[j]) <= d) {  
                     g[i][j] = g[j][i] = true;  
                }  
           }  
      char c;  
      while (cin >> c) {  
           int p, q;  
           if (c == 'O') {  
                cin >> p; p--;  
                on[p] = 1;  
                for (int i = 0; i < n; i++) {  
                     if (g[p][i] && p != i && on[i]) {  
                          union_sets(p, i);  
                     }  
                }  
           }  
           else if (c == 'S') {  
                cin >> p >> q; p--; q--;  
                if (find_set(p) == find_set(q)) {  
                     cout << "SUCCESS" << endl;  
                }  
                else {  
                     cout << "FAIL" << endl;  
                }  
           }  
           else {  
                break;  
           }  
      }  
      return 0;  
 }  

POJ.2184 Cow Exhibition

1.Problem
http://poj.org/problem?id=2184

2.Idea
dp[i][j]: Maximum sum of F, when using first i elements, and total S is j. Then, updating table like 0-1 knapsack problem. To save memory, re-use the table. Using map does not meet the time limit.

3.Source

 #define MAX_RANGE (100*2000+2)  
 #define offset 100000  
 int dp[2][MAX_RANGE];  
 int n;  
 int S[102];  
 int F[102];  
 int max(int x, int y) { return x>y ? x : y; }  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> S[i] >> F[i];  
      }  
      for (int i = 0; i < MAX_RANGE; i++) {  
           dp[0][i] = dp[1][i] = -INF;  
      }  
      int cur, next;  
      dp[0][offset] = 0;  
      for (int i = 0; i < n; i++) {  
           cur = i & 1; next = 1 - cur;  
           for (int i = 0; i < MAX_RANGE; i++) dp[next][i] = -INF;  
           for (int j = 0; j < MAX_RANGE; j++) {  
                if (dp[cur][j] != -INF) {
                     //not using i'th cow  
                     dp[next][j] = max(dp[next][j], dp[cur][j]);  

                     //using i'th cow
       dp[next][j + S[i]] = max(dp[next][j + S[i]], dp[cur][j] + F[i]);  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = offset; i < MAX_RANGE; i++) {  
           if (dp[n&1][i] >= 0) ans = max(ans, i - offset + dp[n&1][i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.2392 Space Elevator

1.Problem
http://poj.org/problem?id=2392

2.Idea
dp[j]: Can reach to heights of j.
First sort all blocks by possible heights limit - a_i. Then update the dp table for each block type h_i.

3.Source

 struct Block {  
      int a, h, c;  
      bool operator < (const Block &A)const {  
           return A.a > a;  
      }  
 } Blocks[402];  
 int k;  
 int dp[40004];  
 int main()  
 {  
      cin >> k;  
      for (int i = 0; i < k; i++) {  
           int A, H, C;  
           cin >> H >> A >> C;  
           Blocks[i].h = H;  
           Blocks[i].a = A;  
           Blocks[i].c = C;  
      }  
      sort(Blocks, Blocks + k);  
      dp[0] = true;  
      for (int i = 0; i < k; i++) {  
           for (int j = 40000; j >= 0; j--) {  
                if (dp[j]) {  
                     for (int g = 1; g <= Blocks[i].c; g++) {  
                          if (j + Blocks[i].h * g <= Blocks[i].a) dp[j + Blocks[i].h * g] = true;  
                          else break;  
                     }  
                }  
           }  
      }  
      int ans;  
      for (int i = 40000; i >= 0; i--) {  
           if (dp[i]) {  
                ans = i;  
                break;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ. 3666 Making the Grade

1.Problem
http://poj.org/problem?id=3666

2.Idea
See this.

3.Source

 ll a[2003];  
 ll h[2003];  
 int n;  
 ll dp[2003][2003];  
 ll Min(ll a, ll b)  
 {  
      if (a > b) return b;  
      else return a;  
 }  
 ll solve()  
 {  
      for(int i=0;i<2003;i++)  
           for (int j = 0; j < 2003; j++) {  
                dp[i][j] = 1 << 30;  
           }  
      dp[0][0] = 0;  
      for (int i = 0; i < 2003; i++) {  
           ll minCost = 1 << 30;  
           for (int j = 0; j < 2003; j++) {  
                minCost = Min(minCost, dp[i][j]);  
                dp[i + 1][j] = minCost + abs((long)a[i] - (long)h[j]);  
           }  
      }  
      ll ans = 1 << 30;  
      for (int i = 0; i < n; i++) {  
           ans = Min(ans, dp[n][i]);  
      }  
      return ans;       
 }  
 int main()  
 {  
      ll ret = (1 << 30);  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> a[i];  
           h[i] = a[i];  
      }  
      //asc  
      sort(h, h + n);  
      ret = Min(ret, solve());  
      //desc  
      reverse(a, a + n);  
      sort(h, h + n);  
      ret = Min(ret, solve());  
      cout << ret << endl;  
      return 0;  
 }  

POJ.1065 Wooden Sticks

1.Problem
http://poj.org/problem?id=1065

2.Idea
According to Dilworth Theorem, minimum number of ordered subtest is equal to the length of longest non-decreasing subsequence.

3.Source

 struct WoodenStick {  
      int l, w;  
      bool operator < (const WoodenStick &a)const {  
           if (l == a.l) return w < a.w;  
           else return l < a.l;  
      }  
 } WoodenSticks[5005];  
 int n;  
 int dp[5005];  
 int solve(int n)  
 {  
      memset(dp, -1, sizeof dp);  
      sort(WoodenSticks, WoodenSticks + n);  
      for (int i = 0; i < n; i++) {  
           *lower_bound(dp, dp + n, WoodenSticks[i].w, greater<int>()) = WoodenSticks[i].w;  
      }  
      return lower_bound(dp, dp + n, -1, greater<int>()) - dp;  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           for (int i = 0; i < n; i++) {  
                scanf("%d%d", &WoodenSticks[i].l, &WoodenSticks[i].w);  
           }  
           cout << solve(n) << endl;  
      }  
 }  

POJ. 1631 Bridging signals

1.Problem
http://poj.org/problem?id=1631

2.Idea
We can solve this problem with LIS(Longest Increasing Subsequence).

3.Source

 int t, n;  
 int p[40004];  
 int dp[40004];  
 int lis(int *p, int n) //longest increasing subsequence  
 {  
      for (int i = 0; i < n; i++) dp[i] = INF;  
      for (int i = 0; i < n; i++) {  
           *lower_bound(dp, dp + n, p[i]) = p[i];  
      }  
      return lower_bound(dp, dp + n, INF) - dp;  
 }  
 int main()  
 {  
      cin >> t;  
      while (t) {  
           cin >> n;  
           for (int i = 0; i < n; i++) scanf("%d", &p[i]);  
           printf("%d\n", lis(p, n));  
           t--;  
      }  
      return 0;  
 }  

POJ.2524 Ubiquitous Religions

1.Problem
http://poj.org/problem?id=2524

2.Idea
Using data structure Union Find/Disjoint Set.

3.Source

 int Parent[50004];  
 int Size[50004];  
 int n, m;  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 int main()  
 {  
      int t = 1;  
      while (true) {  
           scanf("%d%d", &n, &m);  
           if (n + m == 0) break;  
           for (int i = 0; i < n; i++) {  
                make_set(i);  
           }  
           for (int i = 0; i < m; i++) {  
                int x, y;  
                scanf("%d%d", &x, &y);  
                x--;  
                y--;  
                union_sets(x, y);  
           }  
           set<int> ans;  
           for (int i = 0; i < n; i++) {  
                ans.insert(find_set(i));  
           }  
           cout << "Case " << t << ": ";  
           cout << ans.size() << endl;            
           t++;  
      }  
      return 0;  
 }  

POJ.2533 Longest Ordered Subsequence

1.Problem
http://poj.org/problem?id=2533

2.Idea
dp[k]: the length of longest sub ordered sequence that ends at s[i].
dp[i] = max{dp[j] + 1 | j=0..i-1}

3.Source

 
 int dp[1003];  
 int a[1003];  
 int n;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> a[i];  
      }  
      dp[0] = 1;  
      int ans = 1;  
      for (int i = 1; i < n; i++) {  
           dp[i] = 1;  
           for (int j = 0; j < i; j++) {  
                if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);  
           }  
           ans = max(ans, dp[i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ. 3280 Cheapest Palindrome

1.Problem
http://poj.org/problem?id=3280

2.Idea
DP[l][r]: the best cost of substring that starts l and ends r. Then the following interval dp is true.
dp[l][r] = dp[l+1][r -1], if s[l] == s[r]
dp[l][r] = min(dp[l+1][r] + cost[s[l]], dp[l][r-1] + cost[s[r]]), if s[l] != s[r]

3.Source

 int n, m;  
 string s;  
 map<char, int> Cost;  
 int dp[2003][2003];  
 int main()  
 {  
      cin >> n >> m;  
      cin >> s;  
      char c;  
      int l, r;  
      for (int i = 0; i < n; i++) {  
           cin >> c >> l >> r;  
           Cost.insert(make_pair(c, min(l, r)));  
      }  
      for (int len = 1; len < m; len++) {  
           for (int i = 0, j = len; j < m; i++, j++) {  
                if (s[i] == s[j]) {  
                     dp[i][j] = dp[i + 1][j - 1];  
                }  
                else {  
                     dp[i][j] = min(dp[i + 1][j] + Cost[s[i]], dp[i][j - 1] + Cost[s[j]]);  
                }  
           }  
      }  
      cout << dp[0][m-1] << endl;  
       return 0;  
 }  

POJ.3046 Ant Counting

1.Problem
http://poj.org/problem?id=3046

2.Idea
dp[i][j]: The number of possible ways of making j by the first i families. The following relation is true.
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] +...+ dp[i-1][m], {m = minimum of i's number and j}, dp[i-1][j-f] expressing the set only includes f number of i.

3.Source

 #define MAX_N 1000  
 #define MAX_M 100000  
 #define MOD 1000000  
 int n, m, A, S;  
 int a[MAX_N];  
 int dp[MAX_N + 5][MAX_M + 5];  
 int main()  
 {  
      cin >> n >> A >> S >> m;  
      for (int i = 0; i < A; i++) {  
           int t;  
           cin >> t;  
           a[t]++;  
      }  
      dp[0][0] = 1;  
      int total = 0;  
      for (int i = 1; i <= n; i++) {  
           total += a[i];  
           for (int k = 0; k <= a[i]; k++) {  
                for (int j = total; j >= k; j--) {  
                     dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = S; i <= m; i++) {  
           ans = (ans + dp[n][i]) % MOD;  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3616 Milking Time

Problem
http://poj.org/problem?id=3616

Idea
dp[i]: best answer until i hours. The following recurrent equation is correct.
dp[i] = max(dp[i-1], dp[Inv.start] + v[Inv.value] | Inv ends at i);

Source

 int n, m, r;  
 int dp[2000006];  
 vector<vector<pair<int,int>>> a; // s, v  
 int main()  
 {  
      cin >> n >> m >> r;  
      a.resize(n + r + 1);  
      for (int i = 0; i < m; i++) {  
           int s, t, v;  
           cin >> s >> t >> v;  
           a[t + r].push_back(make_pair(s, v));  
      }  
      int ans = -1;  
      for (int i = 1; i <= n + r; i++) {  
           dp[i] = dp[i - 1];  
           for (int j = 0; j < a[i].size(); j++) {  
                int s = a[i][j].first;  
                int v = a[i][j].second;  
                dp[i] = max(dp[i], dp[s] + v);  
           }  
           ans = max(ans, dp[i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1742 Coins

Problem:
http://poj.org/problem?id=1742

Idea:
dp[i][j]: max leaving (not used) number of a[i] if j is possible to make from first 1..i elements, if not it is -1.

Source:

 const int MAX_K = 100000;  
 int dp[MAX_K + 1];  
 int n, k;  
 int a[111];  
 int m[111];  
 void solve()  
 {  
      memset(dp, -1, sizeof dp);  
      dp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j <= k; j++) {  
                if (dp[j] >= 0)  
                     dp[j] = m[i];  
                else if (j < a[i] || dp[j - a[i]] <= 0)  
                     dp[j] = -1;  
                else  
                     dp[j] = dp[j - a[i]] - 1;  
           }  
      }  
      int ans = 0;  
      for (int i = 1; i <= k; i++)  
           if (dp[i]>=0) ans++;  
      cout << ans << endl;  
 }  
 int main()  
 {  
      while (true) {  
           cin >> n >> k;  
           if (n + k == 0) break;  
           for (int i = 0; i < n; i++) cin >> a[i];  
           for (int i = 0; i < n; i++) cin >> m[i];  
           solve();  
      }  
      return 0;  
 }  

POJ.3181 Dollar Dayz

Problem:
http://poj.org/problem?id=3181

Idea:
Exactly same as knapsack problem with no limit.
dp[i][j]: number of the ways of making j with first i elements.
 - dp[i][j] = dp[i - 1][j] (a[i] > j)
 - dp[i][j] = dp[i - 1][j] + dp[i][j-a[i]] (otherwise)
* the poj judge requires big int test pass, even long long is not possible to get AC.

Source

 ll dp[111][1111];  
 int n, k;  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 1; i <= n; i++) dp[1][i] = 1;  
      for (int i = 2; i <= k; i++)  
           for (int j = 1; j <= n; j++) {  
                if (j < i) dp[i][j] = (dp[i-1][j]) % 1000000000;  
                else if(j == i) dp[i][j] = (dp[i - 1][j] + 1) % 1000000000;  
                else dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % 1000000000;  
           }  
      cout << dp[k][n] << endl;  
      return 0;  
 }  

POJ.2229 Sumsets

1.Problem
http://poj.org/problem?id=2229

2.Idea
dp[i]: the answer when input is i.
We can see the following relation.
dp[i] = dp[i-1] if i is odd (sequence always includes '1', so we can exclude it)
dp[i] = dp[i-1] + dp[i/2] if i is even (first part is include '1' + second part is not include '1')


3.Source

 int n;  
 int dp[1000006];  
 int main()  
 {  
      cin >> n;  
      dp[1] = 1;  
      dp[2] = 2;  
      dp[3] = 2;  
      for (int i = 4; i <= n; i++) {  
           if (i % 2) dp[i] = dp[i - 1] % 1000000000;  
           else dp[i] = (dp[i - 1] + dp[i / 2]) % 1000000000;  
      }  
      cout << dp[n] << endl;  
      return 0;  
 }  

POJ.2385 Apple Catching

1.Problem
http://poj.org/problem?id=2385

2. Idea
define a dp like this, dp[i][j]: the max apple catching number when equal or under j movement and until i'th minut.


3.Source

 int t, w;  
 int a[1003];  
 int dp[1003][33];  
 int main()  
 {  
      cin >> t >> w;  
      for (int i = 0; i < t; i++) cin >> a[i];  
      if (a[0] == 1) {  
           dp[0][0] = 1;  
           dp[0][1] = 0;  
      }  
      else {  
           dp[0][0] = 0;  
           dp[0][1] = 1;  
      }  
      for (int i = 1; i < t; i++) {  
           for (int j = 0; j <= w; j++) {  
                // 0 movement case  
                if (j == 0) {   
                     dp[i][j] = dp[i - 1][j];  
                     if (a[i] == 1) dp[i][j]++;  
                     continue;  
                }  
                // take best of no move / move   
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);  
                if ((a[i] == 1 && j % 2 == 0) || (a[i] == 2 && j % 2 == 1)) dp[i][j]++;  
           }  
      }  
      int ans = 0;  
      for (int j = 0; j <= w; j++) ans = max(ans, dp[t - 1][j]);  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1862 Stripies

1.Problem
http://poj.org/problem?id=1862

2.Idea
Pick the biggest 2 value, and process them, return to queue.

3.Source

 int n;  
 double a[111];  
 priority_queue<double> q;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> a[i];  
           q.push(a[i]);  
      }  
      for (int i = n - 1; i > 0; i--) {  
           double A = q.top(); q.pop();  
           double B = q.top(); q.pop();  
           q.push(2 * sqrt(A * B));  
      }  
      cout << fixed << std::setprecision(3) << q.top() << endl;  
      return 0;  
 }  

POJ.2393 Yogurt factory

1. Problem
http://poj.org/problem?id=2393

2. Idea
Each week, comparing current week cost and last week cost + storage cost, choose the small one.

3. Source

 int n;  
 ll s;  
 ll total = 0;  
 ll cur = 0;  
 int main()  
 {  
      cin >> n >> s;  
      for (int i = 0; i < n; i++) {  
           ll c, y;  
           cin >> c >> y;  
           if (i == 0) {  
                cur = c;  
                total = cur * y;  
                continue;  
           }  
           cur = min(cur + s, c);  
           total += (cur * y);  
      }  
      cout << total << endl;  
      return 0;  
 }  

POJ. 3262 Protecting the Flowers

1.Problem
http://poj.org/problem?id=3262

2.Idea
Sort the cows by damage order, the process in that order all line.

3.Source

 struct Point {  
      ll t, d;  
      bool operator < (const Point &a)const {  
                return t * a.d < d * a.t;  
      }  
 } Points[100005];  
 int n;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> Points[i].t >> Points[i].d;  
      }  
      sort(Points, Points + n);  
      ll ans = 0;  
      int T = 0;  
      for (int i = 0; i < n; i++) {  
           ans += T * Points[i].d;  
           T += (2 * Points[i].t);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3040 Allowance

1.Problem
http://poj.org/problem?id=3040

2.Idea
Need to do 2 run greedy calculation. Build a valid coin combination for a allowance as much as close to value c with the following approach:
first run: Start filling from biggest valued coin, and taking as many as possible
second run: If there is still remainder, this time start use smallest valued coins.

3.Source:

 struct Bill {  
      int v, b;  
      bool operator < (const Bill &a)const {  
           return v > a.v;  
      }  
 } Bills[22];  
 int use[22];  
 int n, c;  
 int k = 0;  
 int ans = 0;  
 int main()  
 {  
      cin >> n >> c;  
      for (int i = 0; i < n; i++) {  
           int v, b;  
           cin >> v >> b;  
           Bills[i].v = v;  
           Bills[i].b = b;  
      }  
      // sort by decreasing order of coin value  
      sort(Bills, Bills + n);  
      while (1) {  
           int rest = c;  
           memset(use, 0, sizeof use);  
           // use coins from biggest size:like 50, 10, 5, 1  
           for (int i = 0; i < n; i++) {  
                int tmp = min(Bills[i].b, rest / Bills[i].v);  
                use[i] = tmp;  
                rest -= tmp * Bills[i].v;  
           }  
           // if still need, this time use coin from smallest value: like 1, 5, 10, 50  
           int i = n - 1;  
           while (rest > 0 && i >= 0) {  
                int tmp = min((Bills[i].b - use[i]), (int)ceil((double)rest / (double)Bills[i].v));  
                use[i] += tmp;  
                rest -= tmp * Bills[i].v;  
                i--;  
           }  
           // if can't fill a full allowance, to leave  
           if (rest > 0) break;  
           // get the max possible allowance number for the current combination  
           int MinUse = INF;  
           for (int i = 0; i < n; i++) {  
                if (use[i]) {  
                     MinUse = min(MinUse, Bills[i].b / use[i]);  
                }  
           }  
           // if can't get any number then leave  
           if (MinUse == INF) break;  
           // subtruct used coins from respective vars  
           for (int i = 0; i < n; i++) {  
                Bills[i].b -= (use[i] * MinUse);  
           }  
           ans += MinUse;            
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1328 Radar Installation

1. Problem
http://poj.org/problem?id=1328

2.Idea
Using greedy method, but not just based on X axis order of icelands, instead, using X axis projection segment.

X axis projection segment

3. Source:

 struct Point {  
      double x, y;  
      double s, e; //projection segment to X axis  
      bool operator < (const Point &a)const {  
           return e < a.e;  
      }  
 } Points[1003];  
 int n, d, flag;  
 int solve()  
 {  
      int ans = 1;  
      sort(Points, Points + n);  
      double r = Points[0].e;  
      for (int i = 1; i < n; i++) {  
           if (r < Points[i].s) {  
                r = Points[i].e;  
                ans++;  
           }  
      }  
      return ans;  
 }  
 int main()  
 {  
      int t = 1;  
      while (1) {  
           scanf("%d%d", &n, &d);  
           if (n + d == 0) break;  
           flag = 0;  
           for (int i = 0; i < n; i++) {  
                int x, y;  
                scanf("%d%d", &x, &y);  
                if (y > d) flag = 1;  
                Points[i].x = (double)x;  
                Points[i].y = (double)y;  
                Points[i].s = x - sqrt((double)d * d - (double)y * y);  
                Points[i].e = x + sqrt((double)d * d - (double)y * y);  
           }  
           printf("Case %d: ", t);  
           if (flag) puts("-1");  
           else printf("%d\n", solve());  
           t++;  
      }  
      return 0;  
 }  

POJ. 1159 Palindrome

1.Problem:
http://poj.org/problem?id=1159

2.Idea:
Using short for less memory usage, and get the longest common substring of reverse string and itself.

3. Source:

 const int MAX_N = 5001;  
 short L[MAX_N][MAX_N];  
 int lcs(string x, string y)  
 {  
      int m = x.length();  
      int n = y.length();  
      int i, j;  
      for (i = 0; i <= m; i++)  
           for (int j = 0; j <= n; j++) {  
                if (i == 0 || j == 0) L[i][j] = 0;  
                else if (x[i - 1] == y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;  
                else L[i][j] = max(L[i - 1][j], L[i][j - 1]);  
           }  
      return L[m][n];  
 }  
 string s, rs;  
 int n;  
 int main()  
 {  
      cin >> n >> s;  
      rs = s;  
      reverse(s.begin(), s.end());  
      int k = lcs(s, rs);  
      cout << n - k << endl;  
      return 0;  
 }  

POJ. 1458 Common Subsequence

1.Problem
http://poj.org/problem?id=1458

2.Idea
Using dp method with 2d array.

3.Source:

 const int MAX_N = 5555;  
 int L[MAX_N][MAX_N];  
 int lcs(char *x, char *y)  
 {  
      int m = strlen(x);  
      int n = strlen(y);  
      int i, j;  
      for (i = 0; i <= m; i++)  
           for (int j = 0; j <= n; j++) {  
                if (i == 0 || j == 0) L[i][j] = 0;  
                else if (x[i - 1] == y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;  
                else L[i][j] = max(L[i - 1][j], L[i][j - 1]);  
           }  
      return L[m][n];  
 }  
 int main()  
 {  
      char x[5555], y[5555];  
      while (scanf("%s%s", &x,&y) != EOF) {  
           cout << lcs(x, y) << endl;            
      }  
      return 0;  
 }  

POJ.3190 Stall Reservations

1.Problem:
http://poj.org/problem?id=3190

2.Idea:
Pick items from earlier starting order, and use priority_queue as data structure to simulate stall stations.

3.Source

 struct Interval {  
      int start, end, num;  
      bool operator < (const Interval &a)const {  
           return end>a.end;  
      }  
 } Cows[50004];  
 bool comp(Interval a, Interval b)  
 {  
      if (a.start == b.start) {  
           return a.end < b.end;  
      }  
      else return a.start < b.start;  
 }  
 int n;  
 int ans[50004];  
 int cur = 1;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d%d", &Cows[i].start, &Cows[i].end);  
           Cows[i].num = i;  
      }  
      sort(Cows, Cows + n, comp);  
      priority_queue<Interval> q;  
      q.push(Cows[0]);  
      ans[Cows[0].num] = cur;  
      for (int i = 1; i < n; i++) {  
           if (q.top().end < Cows[i].start) {  
                int tmp = ans[q.top().num]; q.pop();  
                ans[Cows[i].num] = tmp;  
                q.push(Cows[i]);  
           }  
           else {  
                cur++;  
                ans[Cows[i].num] = cur;  
                q.push(Cows[i]);  
           }  
      }  
      cout << cur << endl;  
      for (int i = 0; i < n; i++) {  
           printf("%d\n", ans[i]);  
      }  
      return 0;  
 }  

POJ.1163 The Triangle

Problem:
http://poj.org/problem?id=1163

Idea:
Using dp method, like at every point, choice the max ancestor's path.

Source:

 
 int n;  
 int g[111][111];  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           for (int j = 1; j <= i + 1; j++) {  
                cin >> g[i][j];  
           }  
      }  
      for (int i = 1; i < n; i++) {  
           for (int j = 1; j <= i + 1; j++) {  
                g[i][j] += max(g[i - 1][j - 1], g[i - 1][j]);  
           }  
      }  
      int ans = 0;  
      for (int j = 0; j < n + 2; j++) ans = max(ans, g[n-1][j]);  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1017 Packets

Problem:
http://poj.org/problem?id=1017

Idea:
Start packing from bigger sized boxes.

Source:

 int c[6];  
 int x, y;  
 void solve()  
 {  
      int ans = 0;  
      //6*6  
      ans += c[5];  
      //5*5  
      ans += c[4];  
      c[0] = max(0, c[0] - 11 * c[4]);  
      //4*4  
      ans += c[3];  
      x = c[1];  
      c[1] = max(0, c[1] - 5 * c[3]);  
      if (c[1] == 0 && c[3]) {  
           c[0] = max(0, c[0] - (c[3]*20 - x * 4));  
      }  
      //3*3  
      ans += (c[2] / 4);  
      if (c[2] % 4 == 3) {  
           ans++;  
           if (c[1]) {  
                c[1]--;  
                c[0] = max(0, c[0] - 5);  
           }  
           else {  
                c[0] = max(0, c[0] - 9);  
           }  
      }  
      else if (c[2] % 4 == 2) {  
           ans++;  
           if (c[1] >= 3) {  
                c[1]-=3;  
                c[0] = max(0, c[0] - 6);  
           }  
           else {  
                x = c[1];  
                c[1] = 0;  
                c[0] = max(0, c[0] - (18 - x * 4));  
           }  
      }  
      else if (c[2] % 4 == 1) {  
           ans++;  
           if (c[1] >= 5) {  
                c[1] -= 5;  
                c[0] = max(0, c[0] - 7);  
           }  
           else {  
                x = c[1];  
                c[1] = 0;  
                c[0] = max(0, c[0] - (18 - x * 4));  
           }  
      }  
      //2*2  
      ans += (c[1] / 9);  
      if (c[1] % 9) {  
           ans++;  
           c[0] = max(0, c[0] - (36 - 4 * (c[1]%9)));  
      }  
      //1*1  
      if (c[0] % 36 == 0) {  
           ans += (c[0] / 36);  
      }  
      else {  
           ans += (1 + c[0] / 36);  
      }  
      cout << ans << endl;  
 }  
 int main()  
 {  
      while (1) {  
           int sum = 0;  
           for (int i = 0; i < 6; i++) {  
                cin >> c[i];  
                sum += c[i];  
           }  
           if (sum == 0) break;  
           solve();  
      }  
      return 0;  
 }  

POJ.3253 Fence Repair

Problem:
http://poj.org/problem?id=3253

Idea:
Always pick smallest 2.

Source:

 int n;  
 priority_queue<int, vector<int>, greater<int>> q;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           int t;  
           cin >> t;  
           q.push(t);  
      }  
      ll ans = 0;  
      for (int i = 1; i < n; i++) {  
           int t1 = q.top(); q.pop();  
           int t2 = q.top(); q.pop();  
           q.push(t1 + t2);  
           ans += (t1 + t2);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

C++ tips

1. Minimum Priority Queue - int

 priority_queue<int, vector<int>, greater<int>> q;  

2. Minimum Priotity Queue - Struct

 struct Interval {  
      int start, end, num;  
      bool operator < (const Interval &a)const {  
           return end>a.end;  
      }  
 }  
 bool comp(Interval a, Interval b)  
 {  
      if (a.start == b.start) {  
           return a.end < b.end;  
      }  
      else return a.start < b.start;  
 }  
 priority_queue<Interval> q;  

3. MOD

 static int MOD = 1000000007;  
 class Solution {  
 public:  
      ll total = 0;  
      ll ansMax = 0;  
      vector<ll> sums;  
      long long sumTree(TreeNode *root) {  
           if (root == NULL) return 0;  
           ll subsum = (root->val + sumTree(root->left) + sumTree(root->right));  
           sums.push_back(subsum);  
           return subsum;  
      }  
      int maxProduct(TreeNode* root) {  
           total = sumTree(root);  
           ll ans = 0;  
           for (int i = 0; i < sums.size(); i++) {  
                ll prod = (total - sums[i]) * sums[i];  
                ans = max(ans, prod);  
           }  
           return ans % MOD;  
      }  
 };  

4.String

 // extract to string  
 #include <iostream>  
 #include <string>  
 int main ()  
 {  
  std::string name;  
  std::getline (std::cin,name);  
 }  

5.Lower_bound

  std::vector<int>::iterator low,up;  
  // returns first equal or greater elements location (or returns end if not found)
  low=std::lower_bound (v.begin(), v.end(), 20); 
  up= std::upper_bound (v.begin(), v.end(), 20);  
  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';  
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';  
  std::cout << "lower_bound at position " << (up - low) << '\n';  

5.String

 #include<string>  
 #include<sstream>  
 int main()  
 {  
      string str, line;  
      while (getline(cin, line)) {  
           istringstream input(line);  
           while (input >> str) {  
             //str process here  
           }  
      }  
      return 0;  
 }  

POJ. 3009 Curling 2.0

Problem:
http://poj.org/problem?id=3009

Idea:
Looking for the minimum answer in 10 steps by dfs. When the stone reach to goal, it has to stop the search (In the code the 'flag' is for this purpose).

Source:

 int f[22][22];  
 int h, w;  
 int sx, sy, gx, gy;  
 int ans = 100;  
 void dfs(int x, int y, int throws)  
 {  
      if (throws >= 10) return;  
      int xx = x;  
      int yy = y;  
      int flag = 0;  
      //up  
      x = xx;  
      y = yy;  
      flag = 0;  
      while (x >=0 && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           x--;  
      }  
      if (flag==0 && x >= 0 && (x +1) != xx) {  
           x++;  
           f[x - 1][y] = 0;  
           dfs(x, y, throws + 1);  
           f[x - 1][y] = 1;  
      }  
      //down  
      x = xx;  
      y = yy;  
      flag = 0;  
      while (x < h && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           x++;  
      }  
      if (flag == 0 && x < h && (x - 1) != xx) {  
           x--;  
           f[x+1][y] = 0;  
           dfs(x, y, throws + 1);  
           f[x+1][y] = 1;  
      }  
      //right  
      x = xx;  
      y = yy;  
      flag = 0;  
      if (x == 2 && y == 1) {  
           int g = 0;  
      }  
      while (y < w && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           y++;  
      }  
      if (flag == 0 && y < w && (y -1) != yy) {  
           y--;  
           f[x][y + 1] = 0;  
           dfs(x, y, throws + 1);  
           f[x][y + 1] = 1;  
      }  
      //left  
      x = xx;  
      y = yy;  
      flag = 0;  
      while (y >= 0 && f[x][y] == 0) {  
           if (x == gx && y == gy) {  
                ans = min(throws + 1, ans);  
                flag = 1;  
                break;  
           }  
           y--;  
      }  
      if ( flag == 0 && y >= 0 && (y+1) != yy) {  
           y++;  
           f[x][y - 1] = 0;  
           dfs(x, y, throws + 1);  
           f[x][y - 1] = 1;  
      }  
      return;  
 }  
 int main()  
 {  
      while (1) {  
           cin >> w >> h;  
           if (w + h == 0) break;  
           ans = 100;  
           for (int i = 0; i<h; i++)  
                for (int j = 0; j < w; j++) {  
                     cin >> f[i][j];  
                     if (f[i][j] == 2) {  
                          sx = i;  
                          sy = j;  
                          f[i][j] = 0;  
                     }  
                     if (f[i][j] == 3) {  
                          gx = i;  
                          gy = j;  
                          f[i][j] = 0;  
                     }  
                }  
           dfs(sx, sy, 0);  
           if (ans < 100) cout << ans << endl;  
           else cout << -1 << endl;  
      }  
      return 0;  
 }  

POJ.1003 Hangover

Problem:
http://poj.org/problem?id=1003

Idea:
n/a

Source:

 int main()  
 {  
      double d;  
      while (1) {  
           //scanf("%f", &d);  
           cin >> d;  
           if (d == 0.00) break;  
           int k;  
           double cur = 0.0;  
           for (k = 1; k < 3000; k++) {  
                cur += (1 / (double)(k + 1));  
                if (cur > d) break;  
           }  
           cout << k << " card(s)" << endl;  
      }  
      return 0;  
 }  

POJ.1007 DNA Sorting

Problem:
http://poj.org/problem?id=1007

Idea:
n/a

Source:

 int getInvs(string s)  
 {  
      int ans = 0;  
      int n = s.size();  
      for(int i=0;i<n;i++)  
           for (int j = i + 1; j < n; j++) {  
                if (s[i] > s[j]) ans++;  
           }  
      return ans;  
 }  
 bool comp(string a, string b)  
 {  
      return getInvs(a) < getInvs(b);  
 }  
 int main()  
 {  
      vector<string> sv;  
      int n, m;  
      cin >> m >> n;  
      for (int i = 0; i < n; i++) {  
           string s;  
           cin >> s;  
           sv.push_back(s);  
      }  
      sort(sv.begin(), sv.end(), comp);  
      for (int i = 0; i < n; i++) {  
           cout << sv[i] << endl;  
      }  
      return 0;  
 }  

POJ.2718 Smallest Difference

Problem:
http://poj.org/problem?id=2718

Idea:
Using std.algortihm next_permutation to generate all possible permutations, and only need to check the 2 numbers that you get when splitting the seq in the middle. Also watch out 0 included 2 number cases.

Source:

 int main()  
 {  
      int t;  
      scanf("%d\n", &t);  
      for (int i = 0; i < t; i++) {  
           int ans = 123456789;  
           vector<int> a;  
           char cc;  
           while (cc = getchar()) {  
                if (cc == '\n') break;  
                if (cc >= '0' && cc <= '9') a.push_back((int)(cc - '0'));  
           }  
           int n = a.size();  
           int m = n / 2;  
           sort(a.begin(), a.end());  
           do {                 
                if ( (a[0] == 0 && m-1 > 0) || (a[m] == 0 && m < n-1) ) continue;  
                int num1 = 0;  
                for (int j = 0; j < m; j++) {  
                     num1 = 10 * num1 + a[j];  
                }  
                int num2 = 0;  
                for (int j = m; j < n; j++) {  
                     num2 = 10 * num2 + a[j];  
                }  
                ans = min(ans, abs(num1 - num2));  
           } while (next_permutation(a.begin(), a.end()));  
           cout << ans << endl;  
      }  
      return 0;  
 }  

POJ.3050 Hopscotch

Problem:
http://poj.org/problem?id=3050

Idea:
Using dfs for exhaustive search.

Source:

 #include<cstdio>  
 #include<queue>  
 #include<string>  
 #include<iostream>  
 #include<vector>  
 #include<set>  
 using namespace std;  
 char g[5][5];  
 set<string> ans;  
 int dx[5] = { 0,0,-1,1};  
 int dy[5] = { -1,1,0,0};  
 void dfs(int i, int j, string res, int cur)  
 {  
      if (cur == 6) {  
           ans.insert(res);  
           return;  
      }  
      for (int k = 0; k < 4; k++) {  
           int nx = i + dx[k];  
           int ny = j + dy[k];  
           if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 ) {  
                dfs(nx, ny, res + g[nx][ny], cur + 1);  
           }  
      }  
      return;  
 }  
 int main()  
 {  
      for (int i = 0; i < 5; i++)  
           for (int j = 0; j < 5; j++) {  
                //scanf("%c", &g[i][j]);  
                cin >> g[i][j];  
           }  
      for (int i = 0; i < 5; i++)  
           for (int j = 0; j < 5; j++) {  
                dfs(i, j, "", 0);  
           }  
      cout << ans.size() << endl;  
      return 0;  
 }  

POJ.3187 Backward Digit Sums

Problem Link:
http://poj.org/problem?id=3187

Idea:
Using binomial coeff

Source:

 int n, sum;  
 vector<int> a;  
 int c[10][10];  
 int main()  
 {  
      // calc binom coeff  
      c[0][0] = 1;  
      for (int i = 1; i < 10; i++) {  
           for (int j = 0; j < 10; j++) {  
                if (j == 0) c[i][j] = 1;  
                else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];  
           }  
      }  
      // take input  
      cin >> n >> sum;  
      for (int i = 1; i <= n; i++) {  
           a.push_back(i);  
      }  
      //store ans  
      vector<string> ans;  
      do {  
           int d = 0;  
           for (int i = 0; i < n; i++) {  
                d += c[n - 1][i] * a[i];  
           }  
           if (d == sum) {  
                string str = "";  
                for (int i = 0; i < n; i++) str += (char)(a[i] + 'a' - 1);  
                ans.push_back(str);  
           }  
      } while (next_permutation(a.begin(), a.end()));  
      sort(ans.begin(), ans.end());  
      for (int i = 0; i < n; i++)  
      {  
           cout << (ans[0][i] - 'a' + 1) << " ";  
      }  
      cout << endl;  
      return 0;  
 }  

POJ.1004 Financial Management

Problem Link:
http://poj.org/problem?id=1004

Idea:
n/a

Source:

 int main()  
 {  
  double d[12];  
  double sum = 0;  
  for (int i = 0; i < 12; i++) {  
  cin >> d[i];  
  sum += d[i];  
  }  
  cout << "$";  
  cout << fixed << std::setprecision(2) << sum / 12 << endl;  
  return 0;  
 }