The Mailboxes Manufacturers ProblemTime Limit:1000MS Memory Limit:65536KTotal Submit:299 Accepted:227DescriptionIn the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easyto blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ⁄ 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?”Can you? And what is the minimum number of crackers that you should ask him to provide you with?You may assume the following:1.If a mailbox can withstand x fire-crackers, it can also withstand x− 1fire-crackers.2.Upon an explosion, a mailbox is either totally destroyed (blown up) orunharmed, which means that it can be reused in another test explosion.Note: If the mailbox can withstand a full load of m fire-crackers, then the manufacturer will of course be satisfied with that answer. But otherwise he is looking for the maximum number of crackers that his mailboxes can withstand.InputThe input starts with a single integer N(1 ≤ N≤ 10) indicating the number of test cases to follow. Each test case is described by a line containing two integers: k and m, separated by a single space.OutputFor each test case print one line with a single integer indicating the minimum number of fire-crackers that is needed, in the worst case, in order to figure out how many crackers the mailbox prototype can withstand.Sample Input41 101 1003 735 100Sample Output555050382495SourceSvenskt Mästerskap i Programmering/Norgesmesterskapet 2002 #include <iostream>using namespace std;const int INF = 1 << 28;int d[11][101][101];int sum(int i, int j) {int ret = 0, k;for (k=i; k<=j; k++) ret += k;return ret;}int max(int a, int b) {return a > b ? a : b;}int main() {int caseTime;int i, j, k, t, K, M, l;scanf("%d", &caseTime);while (caseTime--) {scanf("%d%d", &K, &M);for (i=1; i<=M; i++) {for (j=i; j<=M; j++) {d[1][i][j] = sum(i, j);}}for (k=2; k<=K; k++) {for (l=0; l<M; l++) {for (i=1; i+l<=M; i++) {j = i + l;if (i == j) {d[k][i][j] = i;continue;}d[k][i][j] = INF;for (t=i; t<=j; t++) {int tmp;if (t == i) tmp = d[k][i+1][j];else if (t == j) tmp = d[k-1][i][j-1];else tmp = max(d[k-1][i][t-1], d[k-1][t+1][j]); tmp = max(d[k-1][i][t-1], d[k][t+1][j]);if (d[k][i][j] > t + tmp) d[k][i][j] = t + tmp; }}}}printf("%d\n", d[K][1][M]);}return 0;}Bugs Integrated, Inc.Time Limit:15000MS MemoryLimit:30000KTotal Submit:1180 Accepted:309 Case Time Limit:5000MSDescriptionBugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part ofsome memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.TaskYou are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.InputThe first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).OutputFor each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.Sample Input26 6 51 44 62 23 66 46 5 43 36 16 26 4Sample Output34SourceCEOI 2002CODE:#include <iostream>using namespace std;int g[150][10], blk[10];int d[4][60000];int e[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};int n, m, kn;int can1, can2, b[10][60000];int *l0, *l1, *l2, *l3, *bit0, *bit1, *bit2;void build() {int i, j, tmp;for (i=0; i<e[10]; i++) {j = 0; tmp = i;while (tmp > 0) {b[j][i] = tmp % 3;tmp /= 3;j++;}}}inline int maxt(int a, int b) {return a > b ? a : b;}void solve() {int i, j, k, x, y, a1, a2, p, c;scanf("%d%d%d", &n, &m, &kn);memset(g, 0, sizeof(g));memset(d, 0, sizeof(d));for (i=0; i<kn; i++) {scanf("%d%d", &x, &y);g[x-1][y-1] = 1;}for (i=0; i<m; i++) blk[i] = 1 - g[0][i];for (i=1, c=2; i<n; i++) {for (j=0; j<m; j++) {if (g[i][j]) blk[j] = 0;else blk[j]++;c = (c+1)%4;can1 = (j>0 && blk[j]>2 && blk[j-1]>2);can2 = (j>1 && blk[j]>1 && blk[j-1]>1 && blk[j-2]>1);a1 = 2*e[j]+2*e[j-1];a2 = e[j]+e[j-1]+e[j-2];l0 = d[c]; l1 = d[(c+3)%4]; l2 = d[(c+2)%4]; l3 = d[(c+1)%4];bit0 = b[j];if (j>0) bit1 = b[j-1];if (j>1) bit2 = b[j-2];for (p=0; p<e[m]; p++) {if (bit0[p]) {l0[p] = l1[p-e[j]];} else {l0[p] = l1[p];if (j>0 && !bit1[p]) {if (can1) l0[p] = maxt(l0[p],l2[p+a1]+1);if (can2 && !bit2[p]) l0[p] = maxt(l0[p], l3[p+a2]+1); }}}}}printf("%d\n", d[c][0]);}int main() {build();int caseTime;scanf("%d", &caseTime);while (caseTime--) {solve();}return 0;}Silver Cow PartyTime Limit:2000MS MemoryLimit:65536KTotal Submit:1112 Accepted:326 DescriptionOne cow from each of N farms (1 ≤ N≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X(1 ≤ X≤ N). A total of M (1 ≤ M≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires T i(1 ≤ T i≤ 100) units of time to traverse.Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?Line 1: Three space-separated integers, respectively: N, M, and XLines 2..M+1: Line i+1 describes road i with three space-separated integers: A i, B i, and T i. The described road runs from farm A i to farm B i, requiring T i time units to traverse.OutputLine 1: One integer: the maximum of time any one cow must walk.Sample Input4 8 21 2 41 3 21 4 72 1 12 3 53 1 23 4 44 2 3Sample Output10HintCow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.USACO 2007 February Silver#include <iostream>using namespace std;const int INF = 1 << 28;int adj[1001][1001], adjw[1001][1001], na[1001];int n, m, x;//heap sink,swim,getmin,insert参数均为外部编号,wt为其权值int heap[100001], id[100001], hsize;int *key;void init(int s, int *wt) {int i;hsize = s;key = wt;for (i=1; i<=hsize; i++) {heap[i] = i;id[i] = i;}}void swim(int u) {int p = id[u], q = p >> 1, ku = key[u];while (q && ku < key[heap[q]]) {id[heap[q]] = p;heap[p] = heap[q];p = q;q = p >> 1;}id[u] = p;heap[p] = u;}void sink(int u) {int p = id[u],q = p << 1, ku = key[u];while (q <= hsize) {if (q < hsize && key[heap[q+1]] < key[heap[q]]) q++;if (key[heap[q]] >= ku) break;id[heap[q]] = p;heap[p] = heap[q];p = q;q = p << 1;}id[u] = p;heap[p] = u;}int getmin() {int ret = heap[1];id[ret] = -1;id[heap[hsize]] = 1;heap[1] = heap[hsize];hsize--;sink(heap[1]);return ret;}void insert(int u) {heap[++hsize] = u;id[u] = hsize;swim(u);}void build() {int i;for (i=hsize/2; i>0; i--) sink(heap[i]); }bool isEmpty() {return hsize == 0;}int dijkstraHeap(int beg, int end=-1) {int i, j, k, u, v, w;int dist[1001], chk[1001];for (i=1; i<=n; i++) {dist[i] = INF;chk[i] = 0;}init(n, dist);dist[beg] = 0; swim(beg);while (!isEmpty()) {u = getmin();if (u == end) break;chk[u] = 1;for (i=0; i<na[u]; i++) {v = adj[u][i];w = adjw[u][i];if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w;swim(v);}}}if (end == -1) return dist[n];return dist[end];}int main() {int i, j, k, u, v, w;int val[1001];scanf("%d%d%d", &n, &m, &x);for (i=0; i<m; i++) {scanf("%d%d%d", &u, &v, &w);adj[u][na[u]] = v;adjw[u][na[u]] = w;na[u]++;}dijkstraHeap(x);memcpy(val, key, sizeof(val));int ans = 0;for (i=1; i<=n; i++) {int tmp = dijkstraHeap(i,x);if (tmp+val[i] > ans) ans = tmp + val[i]; }printf("%d\n", ans);return 0;}。