饑餓的WZK

jzoj 1988

題目大意：

有很多個點，并且給出n個區間，問在選的區間不重復的前提下，選的區間的點數總和最大是多少

輸入樣例

3 1 3 7 8 3 4

輸出樣例

5

數據范圍

對于100%的數據：1<=N<=2000，1<=B<=1000。

解題思路：

先按結束的位置給區間 們 排個序，然后記錄下在當前區間前且能和當前區間一起選的區間中最后的區間（$last$），然后設$f[i]$為前$i$個區間的最大值，然后可以得出一下方程
$$f[i]=max(f[i?1],f[a[i].last]+a[i].num)$$

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,f[2500]; struct rec {int begin,end,num,last; }a[2500]; bool cmp(rec x,rec y){return x.end<y.end;} int main() {scanf("%d",&n);for (int i=1;i<=n;++i){scanf("%d %d",&a[i].begin,&a[i].end);a[i].num=a[i].end-a[i].begin+1;//數字和}sort(a+1,a+1+n,cmp);//排序for (int i=1;i<=n;++i)for (int j=i-1;j>0;--j)if (a[j].end<a[i].begin)//記錄last{a[i].last=j;break;}for (int i=1;i<=n;++i)f[i]=max(f[i-1],f[a[i].last]+a[i].num);//要不不選，選了就和上一個可以一起有的一起選printf("%d",f[n]);return 0; }

總結

以上是生活随笔為你收集整理的【DP】饥饿的WZK（jzoj 1998）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。