（水题）洛谷

水题）洛谷"/>

（水题）洛谷

很明显时间是一个维度，按照时间顺序决策就行了。
dp[i]表示以时间i为结尾所能达到的最长演讲时间。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;int n;
struct Node{int p,k;Node(){};Node(int _p,int _k):p(_p),k(_k){};
}node[10005];bool cmp(Node &n1,Node &n2){if(n1.k!=n2.k)return n1.k<n2.k;elsereturn n1.p<n2.p;
}int dp[30005];int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&node[i].p,&node[i].k);}sort(node+1,node+1+n,cmp);int i=1;memset(dp,0,sizeof(dp));for(int t=1;t<=30000;t++){dp[t]=dp[t-1];if(t<node[i].k)continue;while(t==node[i].k){dp[t]=max(dp[t],dp[node[i].p]+node[i].k-node[i].p);i++;}}printf("%d\n",dp[30000]);
}

转载于:.html