A2.

Problem A2:

问题描述：(略)

问题分析：这是一个动态规划问题。可以先搜索网格中钱数最大值，按降序依次搜索相应钱数的网格可以收集到

的最大钱数，直到(0,0)格。采用一个辅助网格记录搜索时每一网格能收集到的最大钱数。对每一搜索网格，将自身钱数与

横竖可以跳跃范围内网格收集钱数最大值相加为当前网格可以收集的最大钱数。

算法分析：算法扫描所有网格，时间O(A*4k*n2)，A为网格最大值与(0,0)值之差。除网格占用空间，需要辅助空

间O(n2)。

/******************************************************************** Problem A2 Filename: Hopscotch.cpp Author: Adn@BYHH SN: A5005 *********************************************************************/ #include <iostream> #include <fstream> using namespace std; #define MAX_N 100 int grid[MAX_N][MAX_N]; int afli_grid[MAX_N][MAX_N]; int find_in_grid(int n) { int _maxVal = 0; for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (grid[i][j] > _maxVal) _maxVal = grid[i][j]; return _maxVal; } inline bool vaild_index(int i, int j ,int n) { return (i < n && i >=0 && j < n && j >= 0); } void collect_money(int n, int k) { //int maxcollection = grid[0][0]; int _maxVal ; for (int range = find_in_grid(n); range >= grid[0][0]; range--) { for (int i=0; i<n; i++) for (int j=0; j<n; j++) { if (grid[i][j] == range) { afli_grid[i][j] = grid[i][j]; _maxVal = 0; for (int _setp = 1; _setp <= k; _setp++) { /* as shown below. for every grid it will find the max-money can be collected, because the search is from max to min, so it can make sure every collecting is the maximum. */ /**********4*************************/ if (vaild_index(i+_setp, j, n)) /**********3*************************/ if (grid[i][j] < grid[i+_setp][j] & /**********2*************************/ & _maxVal < afli_grid[i+_setp][j]) /**********1*************************/ _maxVal = afli_grid[i+_setp][j]; /**k****321+123***k******************/ if (vaild_index(i-_setp, j, n)) /**********1*************************/ if (grid[i][j] < grid[i-_setp][j] /**********2*************************/ && _maxVal < afli_grid[i-_setp][j]) /**********3*************************/ _maxVal = afli_grid[i-_setp][j]; /************************************/ if (vaild_index(i, j+_setp, n)) /************************************/ if (grid[i][j] < grid[i][j+_setp] /************************************/ && _maxVal < afli_grid[i][j+_setp]) /************************************/ _maxVal = afli_grid[i][j+_setp]; /**********k*************************/ if (vaild_index(i, j-_setp, n)) /************************************/ if (grid[i][j] < grid[i][j-_setp] /************************************/ && _maxVal < afli_grid[i][j-_setp]) /************************************/ _maxVal = afli_grid[i][j-_setp]; } afli_grid[i][j] += _maxVal; } } } return ; } int main(int argc, char* argv[]) { int _testNum, n, k; fstream hopscotch("hopscotch.in", ios_base::in); if (!hopscotch) { cout << "error: unable to open input file." << endl; return -1; } hopscotch >> _testNum; while (_testNum--) { hopscotch >> n >> k; for (int i=0; i<n; i++) for (int j=0; j<n; j++) hopscotch >> grid[i][j]; collect_money(n, k); cout << afli_grid[0][0] << endl; cout << endl; } return 0; }

A4.

/* Problem A4: 问题描述：(略) 问题分析：问题可以转换为在如下网格中求从(0,0)到(m,n)的路径数。如图示，记到(m,n)的路径数为w(m,n),有 w(m,n)=w(m-1,n)+w(m,n-1)； w(m,0)=1; w(n,n)=w(n,n-1); (m,0) (m,0) /\ /\ /\/\ /\/\(m,n-1) /\/\/\ /\/\/\ /\/\/\/(m,n) /\/\/\/(m,n) (0,0)/\/\/\/ (0,0)/\/\/\/(m-1,n) (m-2,n) 算法采用一个长度为m的数组来计算w(m,n)，循环n次每次计算其中的w(m,1...n)。 算法分析：算法包括三个个循环，其中计算排列数时间复杂度O((2m－n)*n/2)，计算阶乘时间复杂度O(m)+O(n)。 需要辅助空间O(m) */ /******************************************************************** Problem A4 Filename: BuytheTicket.cpp Author: Adn@BYHH SN: A5005 *********************************************************************/ #include <iostream> #include <fstream> using namespace std; #define MAX_M 10000 long waygrid[MAX_M + 1]; int factorial(int _n) { int retVal = 1; if (_n) { for (int i = 1; i <= _n; i++) retVal *= i; } return retVal; } void count_gridway(int m, int n) { memset(waygrid, 0, sizeof(waygrid)); waygrid[0] = 1; // time O(m*n) for (int i = 1; i <= (n + 1); i++) for (int j = i; j <= m; j++) waygrid[j] += waygrid[j -1]; } int main(int argc, char* argv[]) { int m, n; int _testNum = 0; fstream ticket("ticket.in", ios_base::in); if ( !ticket ) { cout << "error: unable to open input file." << endl; return -1; } ticket >> m >> n; while ( m || n) { _testNum++; cout << "Test #" << _testNum << ":" << endl; if (m < n) { cout << "0" << endl; } else { count_gridway(m, n); // final count should be N*m!*n! cout << waygrid[m] * factorial(m) * factorial(n) << endl; } ticket >> m >> n; } return 0; }

A5.

Problem A5:

问题描述：(略)

问题分析：对于这个问题，记录每个设备的启动、停止，将这些操作进行排序，按时间顺序计算需要的供电量，

判断。算法中注意的一个问题是，考虑同一时刻可能同时有设备启动停止，认为停止的操作优先计算。

算法分析：算法中对每一组数据的处理时间包括：排序O(n*log(n))＋轮算O(2n)。算法使用STL，VC7.1编译。

/******************************************************************** Problem A5 Filename: PowerManagement.cpp Author: Adn@BYHH SN: A5005 *********************************************************************/ #include <iostream> #include <fstream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <functional> using namespace std; typedef pair<string, int> equipment; typedef pair<int, int> powermanage; typedef vector<equipment>::iterator _log_It; // overloaded find() for pair equipment _log_It find(_log_It _First, _log_It _Last, const string& _Val) { // find first matching _Val for (; _First != _Last; ++_First) if ((*_First).first == _Val) break; return (_First); } int main(int argc, char* argv[]) { // i use 2 vectors to store the equipment and operating data vector<equipment> equipmentArray; vector<powermanage> operateOrder; fstream powerin("power.in", ios_base::in); if ( !powerin ) { cout << "error: unable to open input file." << endl; return -1; } int _eq_n; string _str; int _power_req; powerin >> _eq_n; // equipment quantity while (_eq_n--) { // get the equipment data powerin >> _str >> _power_req; equipmentArray.push_back(make_pair(_str, _power_req)); } // in some circumstance, i may need overloaded // operator < to operate pair1 < pair2 using namespace std::rel_ops; int _op_num, _power_supply; int up_time, down_time; while (!powerin.eof()) { powerin >> _op_num >> _power_supply; while (_op_num--) { // record all operations as a equipment up and down // powerin >> _str >> up_time >> down_time; operateOrder.push_back((make_pair(up_time, find(equipmentArray.begin(), equipmentArray.end(), _str)->second ))); // positive number as equipment up, and the negative down operateOrder.push_back(make_pair(down_time, -(find(equipmentArray.begin(), equipmentArray.end(), _str)->second) )); } // sort the operator list, make sure the vector // arranged from later time to earlier sort(operateOrder.begin(), operateOrder.end(), greater<powermanage>()); int max_power_needed = 0; int cur_power_needed = 0; int cur_time = 0; bool time_changed; bool power_exceed = false; while ( !operateOrder.empty() ) { if (operateOrder.back().first == cur_time) { time_changed = false; } else { time_changed = true; if (cur_power_needed > _power_supply) { cout << "The power will be out at time " << cur_time; cout << " because the power is " << cur_power_needed << " Watts and overloaded." << endl; power_exceed = true; // clear the vector for next operation list operateOrder.clear(); break; } } cur_power_needed += operateOrder.back().second; if (time_changed) { // suggest such condition that at one time // a equipment is down and another is up, // we set the down operation first cur_time = operateOrder.back().first; if (cur_power_needed > max_power_needed) max_power_needed = cur_power_needed; } operateOrder.pop_back(); } if (!power_exceed) { // power exceed output cout << "The maximum power needed is " << max_power_needed << " Watts."<< endl; } } return 0; }