数字三角形模型
摘花生
- 思路：
- 根据数据范围以及求最大值我们可以得知是动态规划的题目
- 状态表示：
f[i][j]：走到（i，j）能够摘到的花生的集合。属性：最大值 - 状态转移：用当前的状点更新下一个点：
f[nex][ney] = max(f[nex][ney], f[i][j] + a[nex][ney])
- 代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e2 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N][N], f[N][N];
int dx[] = {0, 1};
int dy[] = {1, 0};
signed main()
{
int t;
cin >> t;
while(t --)
{
memset(f, 0, sizeof f);//初始化f为0
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
f[1][1] = a[1][1];
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
//遍历向右，向左的合法位置
for(int k = 0; k < 2; k ++)
{
int nex = i + dx[k], ney = j + dy[k];
if(nex < 0 || nex > n || ney < 0 || ney > m) continue;
f[nex][ney] = max(f[nex][ney], f[i][j] + a[nex][ney]);
}
}
}
cout << f[n][m] << endl;
}
return 0;
}
最低通行费
- 思路：
- 大体思路同摘花生
- 求的最小值，所以f应该初始化为INF
- 代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e2 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N][N], f[N][N];
int dx[] = {0, 1};
int dy[] = {1, 0};
signed main()
{
memset(f, 0x3f, sizeof f);
int n;
cin >> n;
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= n; j ++) cin >> a[i][j];
}
f[1][1] = a[1][1];
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
for(int k = 0; k < 2; k ++)
{
int nex = i + dx[k], ney = j + dy[k];
if(nex < 0 || nex > n || ney < 0 || ney > n) continue;
f[nex][ney] = min(f[nex][ney], f[i][j] + a[nex][ney]);
}
}
}
cout << f[n][n] << endl;
return 0;
}
方格取数
-
思路：
- 类似于摘花生走了两边。
- 首先想到跑两次摘花生的dp，第一次 DP 的结果会对第二次 DP 产生影响，即第一次可以获得最优解，但第二次不一定是最优解。最后答案也不是最优解，所以不能跑两次DP求解。
- 所以我们想到同时走，
f[i1][j1][i1][j2]: 表示从(1, 1) 分别走到(i1,j1),(i2, j2)的最大数值之和 - 其实同时走的话，每次走的步数之和是一样的所以我们可以优化成三维，用k表示i + j,表示走了几步，这时j = k - i, 所以我们就可以用k和i表示j。
- 注意，当两次走到同一个点的时候，该点的数值只能加一次
- 状态表示：
f[k][i1][i2]，表示两次分别走k步，走到(i1, k- i1),(i2, k-i2) 的数值集合，属性：最大值。 - 状态转移: 用四个走法分别更新，（第一次，第二次）走的方向：（下下），（下右），（右下），（右右）
-
代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 20;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N][N];
int f[N * 2][N][N];
signed main()
{
int n;
cin >> n;
int x, y, z;
while(cin >> x >> y >> z && (x != 0 || y != 0 || z != 0))
{
a[x][y] = z;
}
for(int k = 2; k <= n * 2; k ++)
{
for(int i1 = 1; i1 <= n; i1 ++)
{
for(int i2 = 1; i2 <= n; i2 ++)
{
int j1 = k - i1, j2 = k - i2;
if(j1 < 0 || j1 > n || j2 < 0 || j2 > n) continue;
int sum = a[i1][j1];
if(i1 != i2) sum += a[i2][j2];// 当两个人到达的不是同一个点的时候，我们要加两次这个点
int &now = f[k][i1][i2];
//下下
now = max(now, f[k - 1][i1 - 1][i2 - 1] + sum);
//下右
now = max(now, f[k - 1][i1 - 1][i2] + sum);
//右下
now = max(now, f[k - 1][i1][i2 - 1] + sum);
//右右
now = max(now, f[k - 1][i1][i2] + sum);
}
}
}
cout << f[n * 2][n][n] << endl;
return 0;
}
最长上升子序列模型
-
朴素版
-
思路：
==状态表示：==f[i] 以第i个数结尾的上升子序列的集合
==集合划分：==我们以上升子序列的倒数第二数划分
==状态转移：==f[i] = max(f[i], f[j] + 1)
-
代码实现：==复杂度O(N^2)==
//状态表示：f[i], 以第i个数结尾的上升子序列的集合 //状态转移：以序列的倒数第二个为多少进行划分 #include<iostream> using namespace std; const int N = 1e3 + 10; int f[N], a[N]; int main() { int n, res = -1; cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++) { f[i] = 1;//子序列最少为1 for(int j = 1; j < i; j ++) { if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1); } res = max(res, f[i]); } cout << res << endl; return 0; } -
-
二分优化
- 思路：
- 题解中最难理解的地方在于f中序列虽然递增，但是每个元素在原串中对应的位置其实可能是乱的，那为什么这个f还能用于计算最长子序列长度？ 实际上这个f【不用于记录最终的最长子序列】，而是【以f[i]结尾的子串长度最长为i】或者说【长度为i的递增子串中，末尾元素最小的是f[i]】。理解了这个问题以后就知道为什么新进来的元素要不就在末尾增加，要不就替代第一个大于等于它元素的位置。 这里的【替换】就蕴含了一个贪心的思想，对于同样长度的子串，我当然希望它的末端越小越好，这样以后我也有更多机会拓展。
- ==注意：==当要求的子序列不是严格递增的时候，即大于等于的时候，我们应该找==第一个大于x的数==进行替换，而不是大于等于，并且==只要大于等于f[cnt]==就可以加在f[cnt] 后面。
- 实现代码：==复杂度(nlogn)==
#include<iostream> using namespace std; const int N = 1e5 + 10; int f[N], a[N]; int n, cnt = 1; int find(int x) { //查找第一个大于等于x的数 int l = 1, r = cnt; while(l < r) { int mid = (l + r) / 2; if(f[mid] >= x) r = mid; else l = mid + 1; } return l; } int main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; f[1] = a[1]; for(int i = 2; i <= n; i ++) { if(a[i] > f[cnt]) { f[++cnt] = a[i]; } else { int idx = find(a[i]); f[idx] = a[i]; } } cout << cnt << endl; return 0; }
怪盗基德的滑翔翼
- 思路：
- 只能从高向低滑行并且要求经过的楼尽可能的多---> 最长上升子序列问题
- 可以随意选择方向，所以是双向的最长上升子序列问题
- 代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N], f[N];
signed main()
{
int t;
cin >> t;
while(t --)
{
int n, res = 0;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
// 向右飞
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i ++)
{
f[i] = 1;
for(int j = 1; j < i; j ++)
{
if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
res = max(res, f[i]);
}
//向左飞
memset(f, 0, sizeof f);
for(int i = n; i >= 1; i --)
{
f[i] = 1;
for(int j = n; j > i; j --)
{
if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
res = max(res, f[i]);
}
cout << res << endl;
}
return 0;
}
登山
- 思路：
- 根据题意序列应该成一个山峰的形状，所以我们可以从前向后和从后向前分别求一下最长上升子序列，然后枚举相交的转折点。
- 最后答案应该减一，转折点加了两次。
- 代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N], f[N], ff[N];
signed main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
//从前向后的上升子序列的集合
for(int i = 1; i <= n; i ++)
{
f[i] = 1;
for(int j = 1; j < i; j ++)
{
if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
}
//从后向前的上升子序列的集合
for(int i = n ; i > 0; i --)
{
ff[i] = 1;
for(int j = n; j > i; j --)
{
if(a[j] < a[i]) ff[i] = max(ff[i], ff[j] + 1);
}
}
//枚举转折点，求得最大值
int res = 0;
for(int i = 1; i <= n; i ++)
{
res = max(res, f[i] + ff[i] - 1);
}
cout << res << endl;
return 0;
}
友好城市
- 思路：
- 为了保证尽可能建多的桥且不相交，我们应该让建桥两侧的楼的序位置是单调的，即可以求两侧都是单调上升时的最长子序列。
- 两侧同时考虑会有两个变量，我们考虑优化掉一个，可以先把一侧的位置进行排序，这样保证了一侧是单调上升的，然后我们再求另一侧的单调上升的子序列即可。
- 代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> PII;
vector<PII> p;
vector<int> a;
int f[N];
signed main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
int x, y;
cin >> x >> y;
p.push_back({x, y});
}
sort(p.begin(), p.end());
for(auto it : p)
{
a.push_back(it.second);
}
int res = 0;
for(int i = 0; i < a.size(); i ++)
{
f[i] = 1;
for(int j = 0; j < i; j ++)
{
if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
最大上升子序列的和
- 思路：
- 最长上升子序列的变形，我们只需要在f[i]中存子序列的和就可以了
- 注意初始化：==f[i] = a[i]==
- 代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N], f[N];
signed main()
{
int n, res = 0;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
f[i] = a[i];
for(int j = 1; j < i; j ++)
{
if(a[j] < a[i])
{
f[i] = max(f[i], f[j] + a[i]);
}
}
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
导弹拦截
-
思路：
-
第一步求解最长不下降子序列。
-
贪心思想：(1) g[i]记录每个子序列的最后一个值，当有一个新的数加入进来时：
(2) 如果这个数大于所有的g[i], 我们就要新开一个序列， 否则选择大于等于x的最大的g[i] 进行替换。
-
容易得知，g[i] 应该是一个单调上升的子序列。
-
-
结论：==求解最长不下降子序列的个数等于该序列的上升子序列的最大长度。==
-
代码：
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N], f[N], g[N];
int n = 1;
signed main()
{
while(cin >> a[n]) n ++;
n --;
//cout << n << endl;
f[1] = a[1];
int cnt = 1;
for(int i = 2 ; i <= n; i ++)
{
if(a[i] <= f[cnt]) f[++ cnt] = a[i];
else
{
// 替换第一个小于等于a[i]的数
int l = 1, r = cnt;
while(l < r)
{
int mid = (l + r) / 2;
if(f[mid] <= a[i]) r = mid;
else l = mid + 1;
}
f[l] = a[i];
}
}
cout << cnt << endl;
int now = 1;
g[1] = a[1];
for(int i = 2; i <= n; i ++)
{
if(a[i] > g[now]) g[++ now] = a[i];
else
{
int l = 1, r = now;
while(l < r)
{
int mid = (l + r) / 2;
if(g[mid] >= a[i]) r = mid;
else l = mid + 1;
}
g[l] = a[i];
}
}
cout << now << endl;
return 0;
}
京公网安备 11010502036488号