RQNOJ 569 Milking Time：dp & 线段问题

题目链接：https://www.rqnoj.cn/problem/569

题意：

　　在一个数轴上可以摆M个线段，每个线段的起始终止端点给定（为整数），且每个线段有一个分值，问如何从中选取一些线段使得任意两个线段之间的距离大于等于R。每一条线段属于[0，N]。如何选择这些线段，使得分值之和最大？

　　定义：两线段间的距离 = 相邻端点坐标之差的绝对值

题解：

　　讲真。。。这里的N真的没用。。。

　　首先要用左端点从小到大排序。

　　表示状态：

　　　　dp[i] = max score　（选了线段i的当前最大分值）

　　　　i：选了第i个线段

　　找出答案：

　　　　max dp[i]

　　如何转移：

　　　　枚举在i之前的线段j，判断位置是否合法。

　　　　if(lef[i]-rig[j]>=r) dp[i]=max(dp[i],dp[j]+val[i]);

　　边界条件：

　　　　dp[i] = val[i]

　　　　至少选上自己。

AC Code:

 // state expression:

 // dp[i] = max score

 // i: ith segment is selected

 //

 // find the answer:

 // max dp[i]

 //

 // transferring:

 // if lef[i] - rig[j] >= r

 // dp[i] = max dp[j] + w[i]

 //

 // boundary:

 // dp[i] = w[i]

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #define MAX_M 1005

 using namespace std;

 struct Segment

 {

     int lef;

     int rig;

     int val;

     Segment(int _lef,int _rig,int _val)

     {

         lef=_lef;

         rig=_rig;

         val=_val;

     }

     Segment(){}

     friend bool operator < (const Segment &a,const Segment &b)

     {

         return a.lef<b.lef;

     }

 };

 int n,m,r;

 int ans;

 int dp[MAX_M];

 Segment s[MAX_M];

 void read()

 {

     cin>>n>>m>>r;

     for(int i=;i<m;i++)

     {

         cin>>s[i].lef>>s[i].rig>>s[i].val;

     }

 }

 void solve()

 {

     sort(s,s+m);

     for(int i=;i<m;i++)

     {

         dp[i]=s[i].val;

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

         {

             if(s[i].lef-s[j].rig>=r)

             {

                 dp[i]=max(dp[i],dp[j]+s[i].val);

             }

         }

     }

     ans=;

     for(int i=;i<m;i++)

     {

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

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

RQNOJ 569 Milking Time：dp & 线段问题

最新文章

热门文章