Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这道题貌似跟n没啥关系啊...ac了才发现根本没用到n...

Posted by yink at 2021-01-21 23:13:01 on Problem 3616
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,r;
int st[1050],gt[1050],ef[1050];
int dp[1050];
void Sort(int st[],int gt[],int ef[])
{
    int i,j;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=m-i;j++)
        {
            if(gt[j]>gt[j+1])
            {
                swap(st[j],st[j+1]);
                swap(gt[j],gt[j+1]);
                swap(ef[j],ef[j+1]);
            }
        }
    }
}
int main()
{
    int i,temp;
    scanf("%d %d %d",&n,&m,&r);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&st[i],&gt[i],&ef[i]);
    }
    memset(dp,0,sizeof(dp));
    Sort(st,gt,ef);
    dp[1]=ef[1];
    for(i=2; i<=m; i++)
    {
        temp=upper_bound(gt,gt+m,st[i]-r)-1-gt;
        dp[i]=max(dp[i-1],dp[temp]+ef[i]);
    }
    printf("%d",dp[m]);
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator