数字三角形模型
方格取数
分析：
因为要走两次，并且走之后会重新更新为0，所以让两个同时走
如果要同时走，就需要四维，如何优化呢？根据观察，因为两者同时走，所以走的步数是一样的，即\(i1+j1=i2+j2\)，所以可以设置一维是\(k,k=i1+j1=i2+j2\)，就优化成了三维
通过判断\(i1\)是否等于\(i2\)，决定最终要加几次权重
因为\(i1,i2\)都有可能从上或者左来，所以一共有4种状态
状态计算：\(f(k,i1,i2)=max(f(k-1,i1-1,i2-1),f(k-1,i1-1,i2),f(k-1,i1,i2-1),f(k-1,i1,i2))+w[i][j]\)
（依次表示都从上，i1从上i2从左，i1从左i2从上，都从左）
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
| #include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int f[2 * N][N][N], g[N][N];
int n;
int main()
{
cin >> n;
int x, y, z;
while(cin >> x >> y >> z, x | y | z) g[x][y] = z;
for(int k = 2; k <= 2 * n; k++)
{
for(int i1 = 1; i1 <= n; i1++)
{
for(int i2 = 1; i2 <= n; i2++)
{
int j1 = k - i1, j2 = k - i2;
if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
{
int &x = f[k][i1][i2];
int t = g[i1][j1];
if(i1 != i2) t += g[i2][j2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
}
}
cout << f[2 * n][n][n];
return 0;
}
|
传纸条
方格取数是同向一起走，传纸条是相向先后走，为什么所用的代码是一样的呢？
~
既然答案中的i1一定不等于i2，为什么代码中还要写出来呢？
因为不想交的线是由相交的线得到的，所以相交的线是构成最优的必须过程
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
| #include <iostream>
#include <cstring>
using namespace std;
const int N = 60;
int f[2 * N][N][N], g[N][N];
int n, m;
int main()
{
cin >> m >> n;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
cin >> g[i][j];
for(int k = 2; k <= n + m; k++)
{
for(int i1 = 1; i1 <= m; i1++)
{
for(int i2 = 1; i2 <= m; i2++)
{
int j1 = k - i1, j2 = k - i2;
if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
{
int &x = f[k][i1][i2];
int t = g[i1][j1];
if(i1 != i2) t += g[i2][j2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
}
}
cout << f[m + n][m][m];
return 0;
}
|
最长上升子序列
合唱队形
image-20240825143237926
分两步：先求以每个节点为结尾的最长上升子序列，再求以每个节点开始的最长下降子序列；最后相加即可
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
| #include <iostream>
using namespace std;
const int N = 110;
int h[N], f[N], uf[N];
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++)
{
f[i] = 1;
for(int j = 1; j <= n; j++)
if(h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
}
for(int i = n; i >= 1; i--)
{
uf[i] = 1;
for(int j = n; j > i; j--)
if(h[j] < h[i]) uf[i] = max(uf[i], uf[j] + 1);
}
int ans = 0;
for(int i = 1; i <= n; i++) ans = max(ans, f[i] + uf[i] - 1);
cout << n - ans;
return 0;
}
|
拦截导弹
方法一：
- 第一问即求最长不上升子序列的长度
- 第二问要求最少有多少个不上升的子序列，可以\(\color{red}{等价于求最长上升子序列的长度}\)（还不会证明QAQ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], f[N], g[N];
int n = 1;
int ans1, ans2;
int main()
{
while (cin >> w[n]) n++;
n -= 1;
for (int i = 1; i <= n; i++)
{
f[i] = 1, g[i] = 1;
for (int j = 1; j < i; j++)
{
if (w[j] >= w[i]) f[i] = max(f[i], f[j] + 1);
else g[i] = max(g[i], g[j] + 1);
}
ans1 = max(ans1, f[i]);
ans2 = max(ans2, g[i]);
}
cout << ans1 << '\n' << ans2;
return 0;
}
|
方法二：（第二问）
- 维护一个所有子序列末尾的子弹高度的非递减数组
- 如果新的导弹高度高于现在最高的结尾高度，那就新开一个空间放这个导弹
- 如果新的导弹高度低于现在最高的结尾高度，找到大于它的最小高度，加在这个的后面，并修改最高高度
- 求大于它的最小值，可以使用二分进行优化
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>
using namespace std;
const int N = 1010;
int h[N], f[N], g[N];
int n, cnt;
int ans1;
int main()
{
while(cin >> h[++n]);
n -= 1;
for(int i = 1; i <= n; i++)
{
f[i] = 1;
for(int j = 1; j < i; j++)
if(h[j] >= h[i]) f[i] = max(f[i], f[j] + 1);
ans1 = max(ans1, f[i]);
}
cout << ans1 << '\n';
g[0] = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
int x = lower_bound(g, g + cnt, h[i]) - g;
if(x == cnt) g[cnt++] = h[i];
else g[x] = h[i];
cnt = max(x, cnt);
}
cout << cnt;
return 0;
}
|
