首页 > 代码库 > 1272 最大距离 只想到了dp
1272 最大距离 只想到了dp
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1272
离散化后,用dp[i]表示向右,大于等于i这个数字的最大位置
dp[i] = max(dp[i + 1], dp[i])
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 50000 + 20; int a[maxn], dp[maxn], id[maxn]; int n; vector<int>da; void work() { scanf("%d", &n); int top = 0; da.push_back(0); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); da.push_back(a[i]); } sort(da.begin(), da.end()); for (int i = 1; i <= n; ++i) { id[i] = lower_bound(da.begin(), da.end(), a[i]) - da.begin(); } for (int i = n; i >= 1; --i) { dp[id[i]] = max(dp[id[i]], i); } // for (int i = 1; i <= n; ++i) { // cout << id[i] << " "; // } for (int i = n; i >= 1; --i) { dp[i] = max(dp[i], dp[i + 1]); } int ans = 0; for (int i = 1; i <= n; ++i) { ans = max(ans, dp[id[i]] - i); } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
然后这题排个序,然后记录下最小的id就好。
把思维转过来,每个i,去右边找,相当于每个i,向左边找,一样的。
1272 最大距离 只想到了dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。