https://www.cometoj.com/contest/18/problems

A. 夺宝奇兵

 

题意：mm的网格上有n类宝藏，每类有两个，给出坐标，需要按1到n，再从n到1的顺序拿取所有宝藏。求最小距离。

相邻两类宝藏直接比较怎么拿距离最近，就直接拿掉，最后n到n距离固定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int n, m;
pii A, B, C, D;
ll dis(pii a, pii b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}
ll ans;
int main() {
	scanf("%d%d", &n, &m);
	scanf("%lld%lld", &A.first, &A.second);
	scanf("%lld%lld", &B.first, &B.second);
	for (int i = 1; i < n; i++) {
		scanf("%lld%lld", &C.first, &C.second);
		scanf("%lld%lld", &D.first, &D.second);
		ans += min(dis(A, C) + dis(B, D), dis(A, D) + dis(B, C));
		A = C, B = D;
	}
	ans += dis(A, B);
	cout << ans << endl;
	return 0;
}

 

G. 置置置换

 

题意：一个排列满足呈波浪形，求排列数。

dp

把 ii 插入 i−1i-1 的排列中，根据插入位置分成两边，两边仍然是波浪形的排列，就形成了卡特兰数一样的递推式，区别在于左部分点个数必须是偶数，并且要再乘以组合数才是真正的排列数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
int n;
ll a[maxn];
ll C[1010][1010];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)C[i][0] = C[i][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < n; j++)C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}
	a[0] = a[1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= i - 1; j+=2) {
			a[i] = (a[i] + a[j] * a[i - j - 1] % mod*C[i - 1][j] % mod) % mod;
		}
	}
	cout << a[n] << endl;
	return 0;
}