线性动态规划

线性动态规划线性动态规划   处理输入,bag[i]是以i为右界的左界集合 for(int i=0;i<n;i++){     int x,y;     cin>>x>>y;     bag[y].pushback(x); }   dp[i]是第i个bag的时候不重复的最大草数,为每一个bag[i]的x判断找出最大值 dp[i]=max(dp[i],dp[x-1]+i-x+1);//dp[x-1]是第x-1个bag的时候不重复的最大草,避免了重复          #include <bits/stdc++.h> using namespace std; #define N 3000001 vector<int> bag[N]; int n, mx, dp[N]; int main() {       cin >> n;     for (int i = 1; i <= n; i++)     {         int x, y;         cin >> x >> y;         bag[y].push_back(x);         mx = max(mx, y);     }       //bag[i]是一系列以i为右界的左界集合     //dp[i]是第i个bag的时候,不重复最大草数     for (int i = 1; i <= mx; i++)     {         dp[i] = dp[i - 1];         for (int j = 0; j < bag[i].size(); j++)         {             int x = bag[i][j];             dp[i] = max(dp[i], dp[x - 1] + i - x + 1);//i-x+1是一个草区间,找出这个草区间+dp[x-1]最大值,dp[x-1]是第x-1个bag的时候不重复的最大草,避免了重复         }     }     cout << dp[mx]; }        
上一篇:_05-过河卒


下一篇:关于进击acm的错题以及错因以及知识点