SRM 573 DIV2

1、照旧水题~~~，略过

2、贪心算法

 1 #include <iostream> 
 2 #include <string> 
 3 #include <vector> 
 4 #include <cstdlib> 
 5 #include <cmath> 
 6 #include <map> 
 7 #include <stack> 
 8 #include <algorithm> 
 9 #include <list> 
10 #include <ctime> 
11 #include <set> 
12 #include <queue> 
13 typedef long long ll; 
14 using namespace std; 
15 
16 class TeamContestEasy { 
17 public: 
18   int worstRank(vector <int> str){ 
19     int sz=str.size(); 
20     int point=str[1]+str[2]+str[0]-min(str[0],min(str[1],str[2])); 
21     if(3==sz) 
22       return 1; 
23     vector<int> part(sz-3,0); 
24     copy(str.begin()+3,str.end(),part.begin()); 
25     sort(part.begin(),part.end()); 
26     reverse(part.begin(),part.end()); 
27     int sz2=part.size()-1; 
28     int szo=part.size()/3; 
29     int start=0; 
30     int res=0; 
31 /* 
32     for(int i=0;i<=sz2;i++) 
33       cout<<part[i]<<endl; 
34 */ 
35     while(start<sz2){ 
36       if((part[start]+part[sz2])>point){ 
37         res++; 
38         start++; 
39         sz2--; 
40       }else{ 
41         sz2--; 
42       } 
43     } 
44     if(res>szo) 
45       res=szo; 
46     return (res+1); 
47 
48   } 
49 };

3、DP的算法，简化一下，先求一个点Ai到达矩形内某个点Bi的路径数目，然后相乘就是到达所有点A到达点Bi的数目，将点Bi的数目相加就是总数目~~~

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <map>
 7 #include <stack>
 8 #include <algorithm>
 9 #include <list>
10 #include <ctime>
11 #include <set>
12 #include <queue>
13 typedef long long ll;
14 using namespace std;
15 
16 class WolfPackDivTwo {
17 public:
18     int calc(vector<int>, vector<int>, int);
19 };
20 
21 #define maxnum 160
22 #define MOD 1000000007
23 int res[maxnum][maxnum];
24 int dp[2][maxnum][maxnum];
25 const int dx[] = { 0, 0, 1, -1 };
26 const int dy[] = { 1, -1, 0, 0 };
27 bool check(int x, int y) {
28     return x >= 0 && x < maxnum && y >= 0 && y < maxnum;
29 }
30 int WolfPackDivTwo::calc(vector<int> x, vector<int> y, int m) {
31 
32     for (int j = 0; j < maxnum; j++) {
33                 for (int k = 0; k < maxnum; k++) {
34                     res[j][k] =1;
35                 }
36             }
37     for (int i = 0; i < x.size(); i++) {
38         for (int j = 0; j < maxnum; j++) {
39             for (int k = 0; k < maxnum; k++) {
40                 dp[0][j][k] = dp[1][j][k] = 0;
41             }
42         }
43 
44         dp[0][x[i] + 53][y[i] + 53] = 1;
45         for (int t = 1; t < m + 1; t++) {
46             int cur = t % 2;
47             int pre = (t + 1) % 2;
48             for (int j = x[i] + 53 - m - 1; j < x[i] + 53 + m + 1; j++) {
49                 for (int k = y[i] + 53 - m - 1; k < y[i] + 53 + m + 1; k++) {
50                     dp[cur][j][k] = 0;
51                     for (int d = 0; d < 4; d++) {
52                         int tx = j + dx[d];
53                         int ty = k + dy[d];
54                         if (check(tx, ty)) {
55                             int t = dp[cur][j][k] + dp[pre][tx][ty];
56                             dp[cur][j][k] = t % MOD;
57                         }
58                     }
59                 }
60 
61             }
62         }
63         int tk = m % 2;
64         for (int j = 0; j < maxnum; j++) {
65             for (int k = 0; k < maxnum; k++) {
66                 ll t = (ll) res[j][k] * (ll) dp[tk][j][k];
67                 res[j][k] = t % MOD;
68             }
69         }
70     }
71 
72     int ans = 0;
73 
74     for (int i = 0; i < maxnum; i++) {
75         for (int j = 0; j < maxnum; j++) {
76             ans += res[i][j];
77             ans = ans % MOD;
78 
79         }
80     }
81     int resk = ans % MOD;
82     return resk;
83 
84 }