饥饿的拉姆游戏,饥饿的鲨鱼破解版

饥 饿 的 W Z K 饥饿的WZK 饥饿的WZK 题目链接：jzoj 1998 题目大意

有很多个点，并且给出n个区间。
我们要求出在选的区间不重复的前提下，选的区间的点的数量最大是多少。

样例输入 31 37 83 4 样例输出 5 数据范围

对于100%的数据：1<=N<=2000，1<=B<=1000。

思路

这道题用dp来做。
设 f [ i ] f[i] f[i]为从一号窗口到 i i i号窗口，最多可以选多少窗口。
那么对于第 j j j个区间，有两种情况，为选和不选。
那么动态转移方程就为： f [ 区 间 j 的 尾 ] = m a x ( f [ 区 间 j 的 尾 , f [ i ] + 区 间 j 的 窗 口 的 数 量 ) f[区间j的尾]=max(f[区间j的尾,f[i]+区间j的窗口的数量) f[区间j的尾]=max(f[区间j的尾,f[i]+区间j的窗口的数量)

代码 #include<cstdio>#include<iostream>using namespace std;int b,n,f[2001],ans,a[1001][2];bool in[2001];int main(){//freopen("hunger.in","r",stdin);//freopen("hunger.out","w",stdout);scanf("%d",&b);//读入for (int i=1;i<=b;i++){scanf("%d%d",&a[i][0],&a[i][1]);//读入n=max(n,a[i][1]);//求出最后面的窗口in[a[i][1]]=1;//标记}in[0]=1;//初始化for (int i=0;i<=n;i++)if (in[i])for (int j=1;j<=b;j++)if (a[j][0]>i)f[a[j][1]]=max(f[a[j][1]],f[i]+a[j][1]-a[j][0]+1);//动态转移方程for (int i=1;i<=n;i++)ans=max(ans,f[i]);//求出最大值printf("%d",ans);//输出//fclose(stdin);//fclose(stdout);return 0;}