饥饿的奶牛(算是模板题了,求给出N段区间的最大长度和,且区间不能有重叠)

//思路,看成一块一块的草块,一格一格遍历,从左到右
//状态转移方程f[j]=max(f[j],f[i]+j-i+1);
#include <bits/stdc++.h> using namespace std; #define ll long long const int M = 3e6 + 1; vector<int> v[M];//存储当前x的前一个数 int n, m, f[M];//存储每个的y值 int main() { int mx = 0;//找到最右边的 cin >> n; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; v[y].push_back(x - 1);//这里主要是因为,我们是找右界最大的,例如7,8 6,8
    //8的情况下,你有两个区间可以选择,所以你得把两个都加进去
    //用vector数组的方式,维护数据更加方便,而且因为区间不叠加,所以是x-1
mx = max(mx, y); } for (int i = 1; i <= mx; i++) { f[i] = f[i - 1];//这里先更新一下,反正后面会在更新 for (int j = 0; j < v[i].size(); j++) { int k = v[i][j];//找到x-1的那个值, f[i] = max(f[i], f[k] + i - k); } } cout << f[mx] << endl; return 0; }

 

上一篇:Kali Linux中nslookup指令的使用方法5


下一篇:Deltix Round, Summer 2021 E. Equilibrium(线段树)