A2.

/* 动态规划解法, 时间复杂度 n^4 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXSIZE 10000 typedef struct { short price; /* 该格的价值 */ char r, c; /* 行号和列号 */ int result; /* 从左上角走到该格的最大价值 */ } GRID; /* 用于qsort排序的回调函数，用于比较两个格子的价值 */ int grid_comp(const void* g1, const void* g2) { return *(short*)g1-*(short*)g2; } /* n*n个格子 */ GRID grid[MAXSIZE]; int n, k; /* 读取数据 */ void getdata() { int i, j, m; GRID *p = grid; scanf ("%d%d", &n, &k); for (i=0; i<n; ++i) for (j=0; j<n; ++j) { scanf("%d", &m); p->price = m; p->r = i; p->c = j; p++->result = -1; } } /* 动态规划 */ int solve() { GRID *p = grid, *q, *end = grid + n*n - 1; int money, maxmoney = 0; /* 寻找左上角的点，作为动态规划边界条件 */ while (p->r||p->c) ++p; p->result = p->price; /* 按照价值递增顺序求解所有格点 */ do { if (p->result!=-1) /* 如果该格可达 */ /* 检查该格之后所有的格点（即所有价值比其大的格点）的result能否提高 */ for (q=end; q->price > p->price; --q) /* 如果两个格子是一步可达的 */ if (q->r == p->r && p->c <= q->c + k && p->c >= q->c - k || q->c == p->c && p->r <= q->r + k && p->r >= q->r - k) { money = p->result + q->price; if (money > q->result) { /* 更新result */ q->result = money; if (money > maxmoney) { maxmoney = money; } } } } while (++p<=end); return maxmoney; } int main() { int group; // freopen("s2.txt", "r", stdin); scanf ("%d", &group); while (group--) { getdata(); /* 将所有的格子按照价值排序 */ qsort(grid, n*n, sizeof(GRID), grid_comp); printf ("%d\n", solve()); if (group) putchar('\n'); } return 0; }

 A4.

#include <stdio.h> #include <string.h> #include <stdlib.h> #define LEN 100 const int RANGE = 10000; int m, n; short f[101][101][LEN]; // 多位数加法 dest <- dest + src void add(short *dest, const short *src) { int i, j; for (i=j=0; i<LEN; ++i) { dest[i]+=src[i]+j; if (dest[i]>=RANGE) { dest[i]-=RANGE; j=1; } else j=0; } } // 多位数乘法 dest <- src * m void mul(short *dest, const short *src, int m) { div_t d={0,0}; int i; for (i=0; i<LEN; ++i) { d = div(src[i]*m+d.quot, RANGE); dest[i] = d.rem; } } // 多位数输出 void out(const short *src) { int i=LEN-1; while (src[i]==0 && i) --i; printf ("%d", src[i]); while (i>0) printf ("%04d", src[--i]); putchar('\n'); } int main() { int g = 0; int i, j; short reg[LEN]; // 递推求解 while (scanf ("%d%d", &m, &n), m||n) { memset(f[0], 0, sizeof(f[0])); f[0][0][0]=1; for (i=1; i<=m; ++i) { // f[i][0]=f[i-1][0]*i; mul(f[i][0], f[i-1][0], i); for (j=1; j<=i&&j<=n; ++j) { // f[i][j]=i*f[i-1][j]+j*f[i][j-1]; mul(f[i][j], f[i-1][j], i); mul(reg, f[i][j-1], j); add(f[i][j], reg); } } printf ("Test #%d:\n", ++g); out(f[m][n]); } return 0; }

A5.

#include <iostream> #include <fstream> #include <string> #include <algorithm> #include <map> #include <limits> using namespace std; // Power consumption of equipment map<string, int> pwr; // Records struct RECORD { int power; int start; int end; }; // Criterion for comparing two records - by start time // This criterion is used by sort procedure struct { inline bool operator() (const RECORD& p1, const RECORD& p2) { return p1.start < p2.start; } } cmpbystart; // Criterion for comparing two record pointers - by end time // This will be used when manipulating a heap struct { inline bool operator() (const RECORD* p1, const RECORD* p2) { return p1->end > p2->end; } } cmpbyend; // The additional record to be used as a 'Sentinel' const int MAXRECORDS = 800001; RECORD rec[MAXRECORDS]; // All records of a plan RECORD* heap[MAXRECORDS]; // Items that are currently running, stored in a heap main() { // ifstream cin("s5.txt"); int n; string name; // Acquires information of all equipment cin >> n; while (n--) { cin >> name; cin >> pwr[name]; } int power, maxpower, capacity; while ( cin >> n >> capacity) { // Acquires a plan for (int i=0; i<n; ++i) { cin >> name >> rec[i].start >> rec[i].end; rec[i].power = pwr[name]; } // Sorts all the rec by start time sort(rec, rec+n, cmpbystart); // Sets up a 'Sentinel' element rec[n].end = numeric_limits<int>::max(); // Starts simulation int heaplen = 1; heap[0] = rec + n; power = maxpower = 0; for (int i=0; i<n; ++i) { // Removes from the heap all the equipment // that is due to power off before the ith record starts while ( (*heap)->end <= rec[i].start ) { power -= (*heap)->power; pop_heap(heap, heap+heaplen--, cmpbyend); } power += rec[i].power; if (power > capacity) break; // Inserts the ith record into the heap heap[heaplen++] = rec + i; push_heap(heap, heap+heaplen, cmpbyend); if (power > maxpower) maxpower = power; } if (i == n) cout << "The maximum power needed is " << maxpower << " Watts." << endl; else cout << "The power will be out at time " << rec[i].start << " because the power is " << power << " Watts and overloaded." << endl; } }