Problem A: 聪明的田鼠
题解：
dp[k][i]表示走了k步，且在第i行的最大值
最后的结果就是走了n+m-2步，且在第n行的值
代码：
1 #include <map>
2 #include <set>
3 #include <cmath>
4 #include <queue>
5 #include <stack>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 60;
30 // head
31
32 int n, m;
33 int a[MAXN][MAXN];
34 int dp[MAXN * 2][MAXN];
35
36 int main() {
37 cin >> n >> m;
38 rep(i, 1, n + 1) rep(j, 1, m + 1) cin >> a[i][j];
39 dp[0][1] = a[1][1];
40 rep(k, 1, n + m - 1) rep(i, max(1, k + 2 - m), n + 1) if (i <= k + 1)
41 dp[k][i] = max(dp[k - 1][i], dp[k - 1][i - 1]) + a[i][k + 2 - i];
42 cout << dp[n + m - 2][n] << endl;
43 return 0;
44 }
Problem B: 软件安装
题解：
线段树区间更新，区间查询
代码：
1 #include <map>
2 #include <set>
3 #include <cmath>
4 #include <queue>
5 #include <stack>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define all(x) (x).begin(),(x).end()
19 #define pb push_back
20 #define mp make_pair
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1
23 typedef long long ll;
24 typedef vector<int> VI;
25 typedef pair<int, int> PII;
26 const ll MOD = 1e9 + 7;
27 const int INF = 0x3f3f3f3f;
28 const int MAXN = 5e4 + 7;
29 // head
30
31 int cover[MAXN << 2];
32 int lsum[MAXN << 2], rsum[MAXN << 2], msum[MAXN << 2];
33
34 void pushup(int rt, int m) {
35 lsum[rt] = lsum[rt << 1], rsum[rt] = rsum[rt << 1 | 1];
36 if (lsum[rt << 1] == m - (m >> 1)) lsum[rt] += lsum[rt << 1 | 1];
37 if (rsum[rt << 1 | 1] == m >> 1) rsum[rt] += rsum[rt << 1];
38 msum[rt] = max(max(msum[rt << 1], msum[rt << 1 | 1]), rsum[rt << 1] + lsum[rt << 1 | 1]);
39 }
40
41 void pushdown(int rt, int m) {
42 if (cover[rt] != -1) {
43 cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
44 lsum[rt << 1] = rsum[rt << 1] = msum[rt << 1] = (cover[rt] ? 0 : m - (m >> 1));
45 lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = msum[rt << 1 | 1] = (cover[rt] ? 0 : m >> 1);
46 cover[rt] = -1;
47 }
48 }
49
50 void build(int l, int r, int rt) {
51 cover[rt] = -1;
52 lsum[rt] = rsum[rt] = msum[rt] = r - l + 1;
53 if (l == r) return;
54 int m = (l + r) >> 1;
55 build(lson);
56 build(rson);
57 }
58
59 void update(int L, int R, int x, int l, int r, int rt) {
60 if (L <= l && r <= R) {
61 cover[rt] = x;
62 lsum[rt] = rsum[rt] = msum[rt] = (x ? 0 : r - l + 1);
63 return;
64 }
65 pushdown(rt, r - l + 1);
66 int m = (l + r) >> 1;
67 if (L <= m) update(L, R, x, lson);
68 if (R > m) update(L, R, x, rson);
69 pushup(rt, r - l + 1);
70 }
71
72 int query(int x, int l, int r, int rt) {
73 if (l == r) return l;
74 pushdown(rt, r - l + 1);
75 int m = (l + r) >> 1;
76 if (msum[rt << 1] >= x) return query(x, lson);
77 else if (rsum[rt << 1] + lsum[rt << 1 | 1] >= x) return m - rsum[rt << 1] + 1;
78 else query(x, rson);
79 }
80
81 int main() {
82 int n, m;
83 cin >> n >> m;
84 build(1, n, 1);
85 while (m--) {
86 int a, b, c;
87 scanf("%d", &a);
88 if (a == 1) {
89 scanf("%d", &b);
90 if (msum[1] < b) {
91 puts("0");
92 continue;
93 }
94 int ans = query(b, 1, n, 1);
95 printf("%d\n", ans);
96 update(ans, ans + b - 1, 1, 1, n, 1);
97 }
98 else {
99 scanf("%d%d",&b, &c);
100 update(b, b + c - 1, 0, 1, n, 1);
101 }
102 }
103 return 0;
104 }
Problem C: V型积木
题解：
最长上升子序列，枚举每个最为最低点，分别求左右两边的LIS，复杂度n³
不过学长说可以用树状数组，nlogn就能解决，万能的树状数组。。
代码：
1 #include <map>
2 #include <set>
3 #include <cmath>
4 #include <queue>
5 #include <stack>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 110;
30 // head
31
32 int n;
33 int a[MAXN];
34 int dp[MAXN];
35
36 int main() {
37 int T;
38 cin >> T;
39 while (T--) {
40 cin >> n;
41 rep(i, 0, n) scanf("%d", a + i);
42 int ans = 0;
43 rep(k, 0, n) {
44 memset(dp, 0, sizeof(dp));
45 int sum = 0, t = 0;
46 per(i, 0, k) rep(j, i + 1, k + 1) if (a[i] > a[j])
47 dp[i] = max(dp[i], dp[j] + 1), t = max(t, dp[i]);
48 if (t == 0) continue;
49 sum += t;
50 t = 0;
51 rep(i, k + 1, n) rep(j, k, i) if (a[i] > a[j])
52 dp[i] = max(dp[i], dp[j] + 1), t = max(t, dp[i]);
53 if (t == 0) continue;
54 sum += t;
55 ans = max(ans, sum + 1);
56 }
57 if (ans == 0) cout << "No Solution" << endl;
58 else cout << n - ans << endl;
59 }
60 return 0;
61 }
Problem D: 最佳地址
题解：
最小费用流，建立一个超级源点s和超级汇点t
coal0表示原有的发电厂，coal1表示当前要新建的发电厂
从s到coal0连一条流量为b，费用为0的边
从s到coal1连一条流量为sum-b，费用为0的边 因为题目说了全部供应，所以剩下的所有煤矿都要供应到新发电厂
然后coal0和coal1都分别和每个煤矿相连，流量就是煤矿的产量a[i]，费用就是c[0][i]和c[1][i]
最后每个煤矿再连接到t，流量为a[i]，费用为0
然后跑一下最小费用流就可以了
点的标号分别为0-m-1为煤矿 m为coal0 m+1为coal1 m+2为s m+3为t 一共m+4个点
代码：
1 #include <map>
2 #include <set>
3 #include <cmath>
4 #include <queue>
5 #include <stack>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 110; //看了测试数据，m和n最大不超过100
30 // head
31
32 int n, b, m, H;
33 int a[MAXN];
34 int h[MAXN];
35 int c[MAXN][MAXN];
36
37 struct edge { int to, cap, cost, rev; };
38 const int MAX_V = 1e4 + 7;
39 int V;
40 vector<edge> G[MAX_V];
41 int dist[MAX_V];
42 int prevv[MAX_V], preve[MAX_V];
43
44 void add_edge(int from, int to, int cap, int cost) {
45 G[from].pb(edge{ to,cap,cost,(int)G[to].size() });
46 G[to].pb(edge{ from,0,-cost,(int)G[from].size() - 1 });
47 }
48
49 int min_cost_flow(int s, int t, int f) {
50 int res = 0;
51 while (f > 0) {
52 memset(dist, 0x3f, sizeof(dist));
53 dist[s] = 0;
54 bool update = true;
55 while (update) {
56 update = false;
57 rep(v, 0, V) {
58 if (dist[v] == INF) continue;
59 rep(i, 0, G[v].size()) {
60 edge &e = G[v][i];
61 if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
62 dist[e.to] = dist[v] + e.cost;
63 prevv[e.to] = v;
64 preve[e.to] = i;
65 update = true;
66 }
67 }
68 }
69 }
70 if (dist[t] == INF) return -1;
71 int d = f;
72 for (int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap);
73 f -= d;
74 res += d*dist[t];
75 for (int v = t; v != s; v = prevv[v]) {
76 edge &e = G[prevv[v]][preve[v]];
77 e.cap -= d;
78 G[v][e.rev].cap += d;
79 }
80 }
81 return res;
82 }
83
84 int main() {
85 int T;
86 cin >> T;
87 while (T--) {
88 cin >> m >> b >> H >> n;
89 int sum = 0;
90 rep(i, 0, m) scanf("%d", a + i), sum += a[i];
91 rep(i, 0, n) scanf("%d", h + i);
92 rep(i, 0, m) scanf("%d", &c[0][i]);
93 PII ans = mp(0, INF);
94 rep(k, 0, n) {
95 rep(i, 0, MAX_V) G[i].clear();
96 rep(i, 0, m) scanf("%d", &c[1][i]);
97 int coal0 = m, coal1 = m + 1, s = m + 2, t = m + 3;
98 V = m + 4;
99 add_edge(s, coal0, b, 0);
100 add_edge(s, coal1, sum - b, 0);
101 rep(i, 0, m) {
102 add_edge(coal0, i, a[i], c[0][i]);
103 add_edge(coal1, i, a[i], c[1][i]);
104 add_edge(i, t, a[i], 0);
105 }
106 int mcf = min_cost_flow(s, t, sum) + H + h[k];
107 if (mcf < ans.second) ans.second = mcf, ans.first = k;
108 }
109 cout << ans.first + 1 << ' ' << ans.second << endl;
110 }
111 return 0;
112 }
Problem E: 寻宝
题解：
从0点(题目中的1，习惯从0开始，所以全都-1计算）跑一下改进版dijkstra
当然求的不是最短路，d[i]表示从0到i的所有路线中 每条路线中的权重最小的值 的最大值
这个只要稍微修改一下就好了
c[i]存的就是有c[i]个宝藏地点 可以携带i个宝藏到达那里，因为最多有k个宝藏，所以超过k的也按k算
最后贪心模拟一下就好了
代码：
1 #include <map>
2 #include <set>
3 #include <cmath>
4 #include <queue>
5 #include <stack>
6 #include <cstdio>
7 #include <string>
8 #include <vector>
9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll MOD = 1e9 + 7;
26 const int INF = 0x3f3f3f3f;
27 const double EPS = 1e-10;
28 const double PI = acos(-1.0);
29 const int MAXN = 8010;
30 // head
31
32 const int MAX_V = MAXN;
33 struct edge { int to, cost; };
34 vector<edge> G[MAX_V];
35 int d[MAX_V];
36 int V;
37
38 void dijkstra() {
39 priority_queue<PII, vector<PII>, greater<PII> > que;
40 d[0] = INF;
41 que.push(PII(INF, 0));
42
43 while (!que.empty()) {
44 PII p = que.top(); que.pop();
45 int v = p.second;
46 if (d[v] > p.first) continue;
47 rep(i, 0, G[v].size()) {
48 edge e = G[v][i];
49 if (d[e.to] < min(d[v], e.cost)) {
50 d[e.to] = min(d[v], e.cost);
51 que.push(PII(d[e.to], e.to));
52 }
53 }
54 }
55 }
56
57 int n, m, k, w;
58 int a[MAXN], c[MAXN];
59
60 int main() {
61 scanf("%d%d%d%d", &n, &m, &k, &w);
62 V = n;
63 rep(i, 0, k) {
64 int t;
65 scanf("%d", &t);
66 a[--t] = 1;
67 }
68 while (m--) {
69 int x, y, z;
70 scanf("%d%d%d", &x, &y, &z);
71 x--, y--;
72 G[x].pb(edge{ y,z });
73 G[y].pb(edge{ x,z });
74 }
75 dijkstra();
76 rep(i, 0, n) if (a[i]) c[min(d[i] / w, k)]++;
77 int sum = 0, sur = 0, ans = k;
78 per(i, 1, k + 1) {
79 if (c[i]) sur += c[i] - 1;
80 else if (sur) sur--;
81 else ans--;
82 }
83 cout << ans << endl;
84 return 0;
85 }