首页 algorithm 算法OJ HUST_VJ

# B - 花店橱窗布置

Practice 4 - Virtual Judge

状态表示：

dp[i][j] 表示对于前 i 朵花放进前 j 个花瓶的最大美学值

初始化：因为没有花时美学值是 0，所以初始化 dp[0][j] = 0

状态转移：

dp[i][j] = max(dp[i][j], d[i - 1][j - 1] + a[i][j], dp[i - 1][j - 2] + a[i][j - 1]...

表示对于前 i 朵花放进前 j 个花瓶的最大美学值可以看做是，前 i - 1 束花放进前 j - 1 个花瓶并将第 i 束花放进第 j 个花瓶、前 i - 1 束花放进前 j - 2 个花瓶并将第 i 束花放进第 j - 1 个花瓶、…… 以此类推求得最大值

因为我们要保证前 i 朵花一定装在大于等于 j 个花瓶中，所以 j 从 i 开始遍历；又因为要保证剩下的花有足够的花瓶装，所以 f - i <= v - j

输出：

使用 place[i][j] = k 表示在前 i 朵花放进前 j 个花瓶的情况下，第 i 朵花在 k

如果要输出第 i 朵花放的花瓶的位置 place[i][j] ，那么就需要输出第 i - 1 朵花放进前 k - 1 个花瓶的情况，于是逆序输出

1
2
3
4
5
6
void print(int f, int v)
{
	if(f == 0) return;
	print(f - 1, place[f][v] - 1);
	cout << place[f][v] << " ";
}

完整代码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int dp[N][N], a[N][N], place[N][N];//dp -> 前i朵花，放进前j个花瓶中的最大美学值 
void print(int f, int v)
{
	if(f == 0) return;
	print(f - 1, place[f][v] - 1);
	cout << place[f][v] << " ";
}
void solve()
{
	int f, v;
	cin >> f >> v;//f花  v花瓶
	for(int i = 1; i <= f; i++)
		for(int j = 1; j <= v; j++)
			cin >> a[i][j];
	memset(dp, 0xc0, sizeof dp);
	for(int j = 0; j <= v; j++) dp[0][j] = 0;//初始化
	for(int i = 1; i <= f; i++)
	{
		//剩下 f - i 束花，放入 v - j 个花瓶中，要求 f - i <= v - j 
		for(int j = i; j <= v + i - f; j++)
		{
			for(int k = i; k <= j; k++)
			{
				if(dp[i - 1][k - 1] + a[i][k] > dp[i][j])
				{
					dp[i][j] = dp[i - 1][k - 1] + a[i][k];
					place[i][j] = k;
				}	
			}
		}	
	}
	cout << dp[f][v] << '\n';
	print(f, v);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

# C - 导弹拦截

Practice 4 - Virtual Judge

对于第一个问题，很显然是求最长不上升子序列，利用 dpdp + 二分即可

对于第二个问题，利用贪心可以发现，如果我们可以将原数组划分成两个不上升子序列，那么第一个不上升子序列中的最小值一定小于第二个不上升子序列的最小值，因为如果第二个的最小值更小的话这个值就可以直接加到第一个序列中。

举个例子：

对于序列 389 207 155 300 299 170 158 65

第一个不上升子序列是 389 300 299 170 158 65

第二个不上升子序列是 207 155

显然，如果第二个子序列的最后一个值如果是 1 ，小于 65 ，那么它一定会被加到第一个子序列中

因此我们可知，第二问其实是要求最长上升子序列

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
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10;
int a[N], b[N], h[N];
void solve()
{
	int x;
	int down = 0, up = 0;
	a[0] = N;
	while(cin >> x)
	{
		//求最长不上升子序列
		if(a[down] >= x) a[++down] = x;
		else
		{
			int t = upper_bound(a + 1, a + down + 1, x, greater<int>()) - a;
			a[t] = x;
		}
		//求最长上升子序列 
		if(b[up] < x) b[++up] = x;
		else
		{
			int t = lower_bound(b + 1, b + up + 1, x) - b;
			b[t] = x;	
		} 
	}
	cout << down << '\n' << up; 
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

# D - Avoid K Partition

Practice 4 - Virtual Judge

暴力做法：O(n2)O(n^2)

状态表示： f[i] 表示对于前 i 个字符的分隔出和不为 k 的方案数

初始化：因为当 i = 0 时，整个字符串不分割就是一种情况

状态转移： if(sum[j~i] != k) f[i] += f[j]

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
28
//暴力版本 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod =  998244353;
const int N = 2e5 + 10;
int f[N];
void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
	int ans = 0;
	f[0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= i - 1; j++)
			if(a[i] - a[j] != k)
				f[i] += f[j];
	cout << f[n] % mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

优化：O(nlogn)O(nlogn)

因为当 a[i] - a[j] != k 时，我们才会让 f[i] += f[j]

那么换一种思路，我们直接找到满足 a[j] == a[i] - k 的 j ，然后用所有的分隔方案数减去满足 a[j] == a[i] - k 的方案数，就可以得到我们要求的方案数

使用 unordered_map<int, int> mp 实现上述功能， mp[i] = j 中存储当和是 i 时有 j 个方案

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
28
29
30
31
//优化版本 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
const int N = 2e5 + 10;
int f[N];
void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
	unordered_map<int, int> mp;
	int ans = 0, sum = 1;//sum存储总的方案数 
	f[0] = 1, mp[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		f[i] = (f[i] + sum - mp[a[i] - k]) % mod;
		mp[a[i]] += f[i];
		sum += f[i];
	}
	cout << f[n] % mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

# E - Shift + Esc

Practice 4 - Virtual Judge

状态表示：

f[i][j][k] 表示在 (i, j) 上旋转 k 次的最小花费

状态转移：

上到下–从 (i−1,j)(i - 1, j) 到 (i,j)(i, j)：因为 i−1i - 1 层的旋转和第 ii 层无关，所以

f[i][j][k]=min(f[i][j][k],mink(f[i−1][j][k′])+a[i][x]+t∗k)f[i][j][k] = min(f[i][j][k], min_k(f[i - 1][j][k']) + a[i][x] + t * k)

（minkmin_k 表示使式子最小的旋转次数 k′k'， a[i][x]a[i][x] 表示旋转之后 (i,j)(i, j) 位置上的值，tt 是旋转一次的花费）

为了方便，我们可以直接使用一个数组 g[i][j]g[i][j] ，用来存储 (i,j)(i, j) 上的最小花费，那么状态转移可以变成

f[i][j][k]=min(f[i][j][k],g[i−1][j]+a[i][x]+t∗k)f[i][j][k] = min(f[i][j][k], g[i - 1][j] + a[i][x] + t * k)

左到右–从 (i,j−1)(i, j - 1) 到 (i,j)(i, j)：

f[i][j][k]=min(f[i][j][k],f[i][j−1][k]+a[i][x])f[i][j][k] = min(f[i][j][k], f[i][j - 1][k] + a[i][x])

初始化：

因为要求找最小花费，所以需要初始化为∞\infty

没走时花费是 0，初始化 g[0][1] = g[1][0] = 0

注意：用 memset 会超时

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 210;
int a[N][N], f[N][N][N], g[N][N];
void solve()
{
	int n, m, t;
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> a[i][j];
	//f[i][j][k] 在第(i, j)上第i行旋转k次的最小花费
	//初始化
//	memset(f, 0x3f, sizeof f);
//	memset(g, 0x3f, sizeof g);会TLE 
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++) 
		{
			g[i][j] = 9e18;
			for (int k = 0; k < m; k++) f[i][j][k] = 9e18;
		}
	g[0][1] = g[1][0] = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int k = 0; k < m; k++)
			{
				int x = (j + k) % m;//左移k位 到j 
				if(x == 0) x = m;
				f[i][j][k] = min(g[i - 1][j] + t * k, f[i][j - 1][k]) + a[i][x];
				g[i][j] = min(g[i][j], f[i][j][k]); 
			}
		}
	}
	cout << g[n][m] << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--) solve();
	return 0;
}

# F - 最长公共子序列

Practice 4 - Virtual Judge

因为题目给定的两个序列是1∼n1\sim n 的全排列

我们知道，如果给定两个序列 1 2 3 4 5 6 和 2 4 3 6 5 1 ，问第一个序列和第二个序列的最长公共子序列，很显然只需要求第二个序列的最长上升子序列即可

这个题目就可以实现如下转换：将第一个序列从 1∼n1\sim n 进行编号，第二个序列的值和第一个序列的编号对应，就相当于将第一个序列转换成 1∼n1\sim 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
28
29
30
31
32
33
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int f[N];
void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1), ma(n + 1), mb(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i], ma[a[i]] = i;
	for(int i = 1; i <= n; i++) cin >> b[i], mb[i] = ma[b[i]];
	//找到mb的最长上升子序列
	int cnt = 0;
	f[++cnt] = mb[1];
	for(int i = 2; i <= n; i++)
	{
		if(mb[i] > f[cnt]) f[++cnt] = mb[i];
		else
		{
			int x = lower_bound(f + 1, f + cnt + 1, mb[i]) - f;
			f[x] = mb[i];
		}	
	} 
	cout << cnt;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

# G - 能量项链

Practice 4 - Virtual Judge

典型的区间 Dp 问题，思考区间 Dp 的模版

1
2
3
4
5
6
7
8
9
10
11
for(int len = 0; len <= n; len++)//区间长度
	{
		for(int i = 1; i + len - 1 <= n; i++)//区间起点
		{
			int j = i + len - 1;//区间终点
			for(int k = i + 1; k < j; k++)//区间分隔
			{
				//状态转移	
			}
		}
	}

有了模版，这道题就迎刃而解了。

对于环形问题，处理技巧是将数组重复两遍。根据题目要求每 3 个数一组，所以 lenlen 从 33 开始遍历，最长到 n+1n + 1，因为有收尾连接的部分。

状态转移： f[i][j] = max(f[i][j], f[i][k] + f[k][j] + v[i] * v[k] * v[j]) ，即对于区间 (i,j)(i, j)，分隔点是 kk 的情况，那么答案就是区间 (i,k)(i, k) 和区间 (k,j)(k, j) 的和，加上新增的合并代价 v[i] * v[k] * v[j]

答案：遍历每一个长度为 n+1n + 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
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110 * 2;
int f[N][N], v[N];
void solve()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> v[i], v[i + n] = v[i];
	for(int len = 3; len <= n + 1; len++)
	{
		for(int i = 1; i + len - 1 <= 2 * n; i++)
		{
			int j = i + len - 1;
			for(int k = i + 1; k < j; k++)
			{
				f[i][j] = max(f[i][j], f[i][k] + f[k][j] + v[i] * v[k] * v[j]);	
			}
		}
	}
	int res = 0;
	for(int i = 1; i <= n; i++) res = max(res, f[i][i + n]);
	cout << res;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}