2011-0002
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
这道题目现在的数据范围已经改成n<=25了，大致算法是这样：
首先，因为我们希望切最多的水果，因此按照贪心的思路，我们如果在某个时刻，要切一些水果，那么我们必然是在所有目前可以切的水果中按照结束时间排序，结束时间早的先切。
基于这个思路，我们可以用f[i][mask]表示在时间i，剩下的水果状态是mask的情况下，我们的最大得分，然后我们枚举切多少水果，然后从mask中依次取当前可以切的结束时间最早的水果。
不过因为mask是指数级的，所以会暴内存。但是因为题目的特殊性（一次至少切3个水果，再加上我们的贪心策略），使得真正被使用到的状态实际上并不多，我们可以用Treap来存储状态。
然后就是时间问题，时间状态数据很大，但是真正有用的时间点最多2n个——即n个水果出现和消失的时间。（任何在中间时刻切的方案都可以移动到这2n个时间点中最近的，这样保证合法，且不会变差）
因此，我们的算法步骤大致如下：
1、将时间点离散化
2、把水果按照结束时间排序
3、初始只有一个状态，然后时间从1开始枚举，每次新得到的状态在下一次循环中使用
4、每一个时间点的每一个状态，临时状态mask1等于当前状态；然后从1～n枚举水果，每找到一个目前已经出现但是还没有切的水果，更新临时状态mask1，同时当前临时水果数加1；每找到一个水果，用临时水果数更新当前临时状态mask（如果是新出现的状态，必须要到下一时间点才能访问）
标程：
#include <cstdio>
#include <cstdlib>
#include <ctime>
int n,ans,tot,max,temp,mask,now,sum,dzhi,root;
int s[26],e[26];
int f[335544],b[335544];
int l[335544],r[335544],aux[335544];
int a[27];
void turn_r(int &i)\\左旋
{
int j=l[i];
l[i]=r[j];
r[j]=i;
i=j;
}
void turn_l(int &i)\\右旋
{
int j=r[i];
r[i]=l[j];
l[j]=i;
i=j;
}
int chazhao(int &i,int xx)\\查找的同时插入
{
int o;
if(i==0)
{
tot++;
i=tot;
aux[i]=rand() % 335544;
b[i]=xx;
l[i]=0;r[i]=0;
f[i]=0;
return i;
} else
if(xx==b[i]) return i; else
if(xx<b[i])
{
o=chazhao(l[i],xx);
if(aux[l[i]]<aux[i]) turn_r(i);
return o;
} else
{
o=chazhao(r[i],xx);
if(aux[l[i]]<aux[i]) turn_l(i);
return o;
}
}
void lisanhua()\\时间点离散化
{
int f[51];
for(int i=1;i<=n;i++) f[i]=s[i];
for(int i=1;i<=n;i++) f[i+n]=e[i];
int temp;
for(int i=1;i<=n+n;i++)
for(int j=i+1;j<=n+n;j++)
if(f[i]>f[j])
{
temp=f[i];f[i]=f[j];f[j]=temp;
}
temp=0;
for(int i=1;i<=n+n;i++)
if(f[i]>f[i-1])
{
temp++;
for(int j=1;j<=n;j++)
{
if(s[j]==f[i]) s[j]=temp;
if(e[j]==f[i]) e[j]=temp;
}
}
max=temp;
}
int main()
{
a[1]=1;
srand(time(0));
for(int i=2;i<=26;i++) a[i]=a[i-1]*2;
int temp;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d %d",&s[i],&e[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(e[i]>e[j])
{
temp=e[i];e[i]=e[j];e[j]=temp;
temp=s[i];s[i]=s[j];s[j]=temp;
} \\先对水果排序
lisanhua();
tot=0;
temp=1;
b[1]=a[n+1]-1;
root=0;
temp=chazhao(root,b[1]);
for(int i=1;i<=max;i++)
{
for(int j=1;j<=temp;j++)
{
mask=b[j];
now=1;
sum=0;
while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++;\\取下一个可行的水果
mask-=a[now];
while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++;\\取下一个可行的水果
mask-=a[now];
while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++；\\取下一个可行的水果
mask-=a[now]; \\先取三个水果
if(now<=n)
{
sum=3;
while(now<=n)
{
dzhi=chazhao(root,mask); \\查找状态
if(f[dzhi]<sum+f[j]) f[dzhi]=sum+f[j]; \\更新状态
while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++;\\取下一个可行的水果
mask-=a[now];
sum++;
}
}
}
temp=tot;
}
ans=0;
for(int i=1;i<=tot;i++)
if(f[i]>ans) ans=f[i];
printf("%d\n",ans);
}
return 0;
}
by hzwlzrj这道题目现在的数据范围已经改成n<=25了，大致算法是这样：
首先，因为我们希望切最多的水果，因此按照贪心的思路，我们如果在某个时刻，要切一些水果，那么我们必然是在所有目前可以切的水果中按照结束时间排序，结束时间早的先切。
基于这个思路，我们可以用f[i][mask]表示在时间i，剩下的水果状态是mask的情况下，我们的最大得分，然后我们枚举切多少水果，然后从mask中依次取当前可以切的结束时间最早的水果。
不过因为mask是指数级的，所以会暴内存。但是因为题目的特殊性（一次至少切3个水果，再加上我们的贪心策略），使得真正被使用到的状态实际上并不多，我们可以用Treap来存储状态。
然后就是时间问题，时间状态数据很大，但是真正有用的时间点最多2n个——即n个水果出现和消失的时间。（任何在中间时刻切的方案都可以移动到这2n个时间点中最近的，这样保证合法，且不会变差）
因此，我们的算法步骤大致如下：
1、将时间点离散化
2、把水果按照结束时间排序
3、初始只有一个状态，然后时间从1开始枚举，每次新得到的状态在下一次循环中使用
4、每一个时间点的每一个状态，临时状态mask1等于当前状态；然后从1～n枚举水果，每找到一个目前已经出现但是还没有切的水果，更新临时状态mask1，同时当前临时水果数加1；每找到一个水果，用临时水果数更新当前临时状态mask（如果是新出现的状态，必须要到下一时间点才能访问）
标程：
#include
#include
#include
int n,ans,tot,max,temp,mask,now,sum,dzhi,root;
int s[26],e[26];
int f[335544],b[335544];
int l[335544],r[335544],aux[335544];
int a[27];
void turn_r(int &i)\\左旋
{
int j=l[i];
l[i]=r[j];
r[j]=i;
i=j;
}
void turn_l(int &i)\\右旋
{
int j=r[i];
r[i]=l[j];
l[j]=i;
i=j;
}
int chazhao(int &i,int xx)\\查找的同时插入
{
int o;
if(i==0)
{
tot++;
i=tot;
aux[i]=rand() % 335544;
b[i]=xx;
l[i]=0;r[i]=0;
f[i]=0;
return i;
} else
if(xx==b[i]) return i; else
if(xx { o=chazhao(l[i],xx); if(aux[l[i]] return o; } else { o=chazhao(r[i],xx); if(aux[l[i]] return o; } } void lisanhua()\\时间点离散化 { int f[51]; for(int i=1;i<=n;i++) f[i]=s[i]; for(int i=1;i<=n;i++) f[i+n]=e[i]; int temp; for(int i=1;i<=n+n;i++) for(int j=i+1;j<=n+n;j++) if(f[i]>f[j]) { temp=f[i];f[i]=f[j];f[j]=temp; } temp=0; for(int i=1;i<=n+n;i++) if(f[i]>f[i-1]) { temp++; for(int j=1;j<=n;j++) { if(s[j]==f[i]) s[j]=temp; if(e[j]==f[i]) e[j]=temp; } } max=temp; } int main() { a[1]=1; srand(time(0)); for(int i=2;i<=26;i++) a[i]=a[i-1]*2; int temp; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d %d",&s[i],&e[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(e[i]>e[j]) { temp=e[i];e[i]=e[j];e[j]=temp; temp=s[i];s[i]=s[j];s[j]=temp; } \\先对水果排序 lisanhua(); tot=0; temp=1; b[1]=a[n+1]-1; root=0; temp=chazhao(root,b[1]); for(int i=1;i<=max;i++) { for(int j=1;j<=temp;j++) { mask=b[j]; now=1; sum=0; while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++;\\取下一个可行的水果 mask-=a[now]; while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++;\\取下一个可行的水果 mask-=a[now]; while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++；\\取下一个可行的水果 mask-=a[now]; \\先取三个水果 if(now<=n) { sum=3; while(now<=n) { dzhi=chazhao(root,mask); \\查找状态 if(f[dzhi] while((now<=n)&&(((mask & a[now])==0)||(s[now]>i))) now++;\\取下一个可行的水果 mask-=a[now]; sum++; } } } temp=tot; } ans=0; for(int i=1;i<=tot;i++) if(f[i]>ans) ans=f[i]; printf("%d\n",ans); } return 0; } by hzwlzrj