10 条题解
-
12
题目要求怪盗基德在逃跑过程中选择一个方向,然后按照该方向的最长上升子序列路线逃跑。我们可以分别计算从左往右和从右往左的最长上升子序列长度,然后取二者的较大值作为结果。
具体解析如下:
- 从左往右计算最长上升子序列长度:
- 初始化一个长度为n的dp数组,其中dp[i]表示以第i幢建筑结尾的最长上升子序列长度。
- 初始时,每个建筑本身都可以作为单独的上升子序列,即dp[i] = 1。
- 从第2个建筑开始遍历,对于每一个建筑i,比较其与前面建筑的高度。
- 如果当前建筑高度heights[i]大于前面建筑的高度heights[j],则将dp[i]更新为dp[j] + 1,其中j为范围[0, i-1]的索引。
- 最终dp数组中的最大值即为从左往右的最长上升子序列长度。
- 从右往左计算最长上升子序列长度:
- 初始化一个长度为n的dp数组,其中dp[i]表示以第i幢建筑开头的最长上升子序列长度。
- 初始时,每个建筑本身都可以作为单独的上升子序列,即dp[i] = 1。
- 从倒数第2个建筑开始遍历,对于每一个建筑i,比较其与后面建筑的高度。
- 如果当前建筑高度heights[i]大于后面建筑的高度heights[j],则将dp[i]更新为dp[j+1] + 1,其中j为范围[i+1, n-1]的索引。
- 最终dp数组中的最大值即为从右往左的最长上升子序列长度。
- 取两个方向的最长上升子序列长度的较大值作为结果,输出结果。
这种解法的时间复杂度为O(n^2),其中n为建筑的数量。通过动态规划的思路,我们可以高效地求解怪盗基德能够经过的最多建筑数量。
#include <iostream> #include <algorithm> #include <vector> using namespace std; int findLongestIncreasingSubsequence(vector<int>& heights) { int n = heights.size(); vector<int> dp(n, 1); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (heights[i] > heights[j]) { dp[i] = max(dp[i], dp[j] + 1); } } } return *max_element(dp.begin(), dp.end()); } int main() { int n; cin >> n; vector<int> heights(n); for (int i = 0; i < n; ++i) { cin >> heights[i]; } int max_left = findLongestIncreasingSubsequence(heights); std::reverse(heights.begin(), heights.end()); int max_right = findLongestIncreasingSubsequence(heights); int max_buildings = max(max_left, max_right); cout << max_buildings << endl; return 0; }
- 从左往右计算最长上升子序列长度:
-
0
我挖了一个坑🕳
#include<iostream> #include<algorithm> using namespace std; int a[10005], d1[10005], d2[10005], f[10005], g[10005]; int main() { int n; cin >> n; for (int i = 1; i <=n; i++) { cin >> a[i]; d1[i] = d2[i] = 100000; } int ans = 0; for (int i = 1; i < n; i++) { int now = lower_bound(d1 + 1, d1 + n + 1, a[i]) - d1; f[i] = now; d1[now] = a[i]; } for(int i=n;i>=1;i--) { int now=lower_bound(d2+1,d2+n+1,a[i])-d2; g[i]=now; d2[now]=a[i]; } for (int i = 1; i < n; i++) { ans = max(ans, f[i]); ans = max(ans, g[i]); } cout << ans; return 0; }
发财了
💴💴💴💴💴💴💴💴💴💴💴💴💴💴💴💴💴💴💴
-
0
题目描述
怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已,怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。初始时,怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?
本题翻译就是求a数组最长上升子序列ans,和最长下降子序列ans1
取最大值输出即可(max)
所以这题应该用
双重循环两个循环解决
核心代码:
cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; d[i]=1000000,d1[i]=1000000; }for(int i=1;i<=n;i++){ int now=lower_bound(d+1,d+n+1,a[i])-d; f[i]=now; d[now]=a[i]; ans=max(ans,f[i]); }for(int i=n;i>=1;i--){ int now=lower_bound(d1+1,d1+n+1,a[i])-d1; f1[i]=now; d1[now]=a[i]; ans1=max(ans1,f1[i]); }cout<<max(ans,ans1);
-
0
题目要求怪盗基德在逃跑过程中选择一个方向,然后按照该方向的最长上升子序列路线逃跑。我们可以分别计算从左往右和从右往左的最长上升子序列长度,然后取二者的较大值作为结果。
具体解析如下:
- 从左往右计算最长上升子序列长度:
- 初始化一个长度为n的dp数组,其中dp[i]表示以第i幢建筑结尾的最长上升子序列长度。
- 初始时,每个建筑本身都可以作为单独的上升子序列,即dp[i] = 1。
- 从第2个建筑开始遍历,对于每一个建筑i,比较其与前面建筑的高度。
- 如果当前建筑高度heights[i]大于前面建筑的高度heights[j],则将dp[i]更新为dp[j] + 1,其中j为范围[0, i-1]的索引。
- 最终dp数组中的最大值即为从左往右的最长上升子序列长度。
- 从右往左计算最长上升子序列长度:
- 初始化一个长度为n的dp数组,其中dp[i]表示以第i幢建筑开头的最长上升子序列长度。
- 初始时,每个建筑本身都可以作为单独的上升子序列,即dp[i] = 1。
- 从倒数第2个建筑开始遍历,对于每一个建筑i,比较其与后面建筑的高度。
- 如果当前建筑高度heights[i]大于后面建筑的高度heights[j],则将dp[i]更新为dp[j+1] + 1,其中j为范围[i+1, n-1]的索引。
- 最终dp数组中的最大值即为从右往左的最长上升子序列长度。
- 取两个方向的最长上升子序列长度的较大值作为结果,输出结果。
这种解法的时间复杂度为O(n^2),其中n为建筑的数量。通过动态规划的思路,我们可以高效地求解怪盗基德能够经过的最多建筑数量。
#include <iostream> #include <algorithm> #include <vector> using namespace std; int findLongestIncreasingSubsequence(vector<int>& heights) { int n = heights.size(); vector<int> dp(n, 1); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (heights[i] > heights[j]) { dp[i] = max(dp[i], dp[j] + 1); } } } return *max_element(dp.begin(), dp.end()); } int main() { int n; cin >> n; vector<int> heights(n); for (int i = 0; i < n; ++i) { cin >> heights[i]; } int max_left = findLongestIncreasingSubsequence(heights); std::reverse(heights.begin(), heights.end()); int max_right = findLongestIncreasingSubsequence(heights); int max_buildings = max(max_left, max_right); cout << max_buildings << endl; return 0; }
- 从左往右计算最长上升子序列长度:
-
-2
#include <iostream> #include <cstring> using namespace std; int n,ans,len; int main(){ cin>>n; int a[n+1],b[n+1],f[n+1],d[n+1]; memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),memset(f,0,sizeof(f)),memset(d,0x3f,sizeof(d)); for (int i=1;i<=n;i++){ cin>>a[i]; b[n-i+1]=a[i]; } for (int i=1;i<=n;i++){ int now=lower_bound(d+1,d+len+1,a[i])-d; f[i]=now,d[now]=min(d[now],a[i]),ans=max(now,ans),len=max(len,now); } memset(f,0,sizeof(f)),memset(d,0x3f,sizeof(d)); for (int i=1;i<=n;i++){ int now=lower_bound(d+1,d+len+1,b[i])-d; f[i]=now,d[now]=min(d[now],b[i]),ans=max(now,ans),len=max(len,now); } cout<<ans; return 0; }
-
-6
头文件可以: #include < bits/stdc++.h > 或者 #include < iostream > 加 #include < algorithm >
int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; d[i] = 100000; d1[i] = 100000; } int ans = 0, ans1 =0; for (int i = n; i >= 1; i--) { int now = lower_bound(d + 1, d + n + 1, a[i]) - d; f[i] = now; d[now] = a[i]; ans=max(ans,f[i]); } for (int i = 1; i <= n; i++) { int now = lower_bound(d1 + 1, d1 + n + 1, a[i]) - d1; f1[i] = now; d1[now] = a[i]; ans1=max(ans1,f1[i]); } cout << max(ans,ans1) << endl; return 0; }
- 1
信息
- ID
- 268
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 929
- 已通过
- 374
- 上传者