codevs3027(dp)

题意: 中文题目诶~

思路: dp

先给所有线段按照右端点值升序 sort 一下, 用 dp[i] 存储以第 i 条线段结尾的线段集合的最大价值,

那么动态转移方程式为: dp[i] = max(dp[i], dp[j] + gel[i].v), 其中 j < i 且 gel[i].l >= gel[j].r

注意 dp[n - 1] 不一定是最大, 维护一个 sol = max(sol, dp[i])

代码:

 #include <iostream>

 #include <stdio.h>

 #include <algorithm>

 using namespace std;

 const int MAXN = 1e3 + ;

 struct node{

     int l, r, v;

 }gel[MAXN];

 int dp[MAXN], vis[MAXN];

 bool cmp(node a, node b){

     return a.r < b.r;

 }

 int main(void){

     int n, indx = , sol = ;

     scanf("%d", &n);

     for(int i = ; i < n; i++){

         scanf("%d%d%d", &gel[i].l, &gel[i].r, &gel[i].v);

     }

     sort(gel, gel + n, cmp);

     for(int i = ; i < n; i++){

         dp[i] = gel[i].v;

         for(int j = ; j < i; j++){

             if(gel[i].l >= gel[j].r){

                 dp[i] = max(dp[i], dp[j] + gel[i].v);

             }

         }

         sol = max(sol, dp[i]);

     }

     printf("%d\n", sol);

     return ;

 }

巴特西

codevs3027(dp)

最新文章

热门文章