Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

【除草】Baltic OI 2010 day2 candies

很久没写了。。。

题意:
给你一个装箱问题(N<=100 Ai<=7000)  记用这些有限物品能拼成的重量种数为Ans
求 把i物品Ai 换成X后 使新的能得到的重量种数Ret最大 同时使X最小 求X和Ret

做法:
这个题我做了一晚上加一上午!!

猜想:
换一个物品 等价于 先去掉这个物品做N-1个物品 最后加入一个物品并更新
(写了个暴力  是符合的)
然后就将问题变为了真正的两问:
第一问,求X使得除了X的N-1个物品能得到的种数Ans'最大
(因为最终方案一样 所以得删一个最没用的)
第二问,添加一个物品 使得最后得到的最大

对于第一问   一个简单的想法便是枚举去掉哪个物品 做100次装箱问题
但是我们还是遇到了瓶颈  做一次装箱问题复杂度O(100^2*7000) 枚举的话 做一次就得0.5秒 根本无法满足
(很不幸我想不到不枚举的方法 只能用区间背包这个不好估计复杂度的来完成 实际效果确实还得TLE)

【我的做法便是将100个物品分为10组 枚举每10个物品 先将另外90个物品做好区间背包 保存这个答案数组
然后对于这10个物品 每次添加9个物品
算下复杂度
原本要放进99*100=9900次物品
现在 90*10+9*9*10=2000次左右 整整减少了5倍!

对于第二问   事实上我们可以发现  添加Y=(∑Ai)-X+1这个物品是肯定可以将方案数增加最多的 因为
假设用N-1个物品能得到的装箱数组是
1 2 3 4 5 6 7 8 9 10 11 12
o x o o o x o o x o   x   x  ....
那么11必然是一个使方案最大可行解 亦可能是最优解
所以我们如果要找一个比Y更优的解 必然要满足原本拥有的所有解加上Y'    原本都不可行!

这样就把问题转化为如下:
对于一个1..700000的布尔数组A 求一个最小的X
使得对于任意一个i A[i]=1 A[i+X]=0。
(很不幸除了枚举X 这一问我也不会做 )

【我的做法
先预处理前缀和  即从1开始到i能拼成的个数
先把这个枚举加些剪枝 将原来拼不成的重量进行枚举
再从这些拼不成的重量里枚举X   因为区间背包算出来的是许多个区间 最后枚举这些区间
对于一个区间[a,b] 如果X是可行的那必然有 sum(a+X,b+X)=0】

事实上这么做居然就过了!因为区间数不太多 我能构造的最牛逼的数据 也只能 O(300000*5000) 这个还是勉强能跑过的
对于官方数据 每个点都能在0.2s内跑过!!

这样终于AC了此题!!

(另外求标准的优美的算法!!!!!!!!!)

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define n 20005
  5 using namespace std;
  6 struct Tintv
  7 {
  8     int x,y;
  9 }    P[n],Q[n],R[n],Ptmp[n];
 10 int len,sum,lentmp,N,M,A[105],list[30];
 11 int H[n],v[n],d[n],HLength,S[1400005];
 12 bool F[1400005];
 13 inline int Calc(int Left,int Right,int u,int v)
 14 {
 15     R[0].x=R[0].y=-2;
 16     for (int l=Left;l<=Right;++l)
 17     if (l<u||l>v)
 18     {
 19         for (int i=1;i<=len;++i)
 20             Q[i].x=P[i].x+A[l],Q[i].y=P[i].y+A[l];
 21         int r=0;
 22         for (int p=1,q=1;p<=len||q<=len;)
 23         if (p<=len&&(q>len||P[p].x<Q[q].x))
 24         {
 25             if (R[r].y+1>=P[p].x)    R[r].y=max(R[r].y,P[p].y);
 26             else    R[++r].x=P[p].x,R[r].y=P[p].y;
 27             ++p;
 28         }
 29         else
 30         {
 31             if (R[r].y+1>=Q[q].x)    R[r].y=max(R[r].y,Q[q].y);
 32             else    R[++r].x=Q[q].x,R[r].y=Q[q].y;
 33             ++q;
 34         }
 35         for (int i=1;i<=r;++i)
 36             P[i]=R[i];
 37         len=r;
 38     }
 39     int tmp=-1;
 40     for (int i=1;i<=len;++i)
 41         tmp+=P[i].y-P[i].x+1;
 42     return tmp;
 43 }
 44 inline bool check(int u)
 45 {
 46     for (int i=1;i<=len;++i)
 47         if (S[P[i].y+u]-S[P[i].x+u-1]>0)    return 0;
 48     return 1;
 49 }
 50 int main()
 51 {
 52     scanf("%d",&N);
 53     for (int i=1;i<=N;++i)
 54         scanf("%d",&A[i]),M+=A[i];
 55     sort(A+1,A+N+1);
 56     int ret=0,Ret=0,tmp;
 57     list[++list[0]]=1;
 58     for (int i=1;i<=N;i+=10)
 59     {
 60         tmp=i+10;
 61         if (tmp>N)    tmp=N+1;
 62         list[++list[0]]=tmp;
 63     }
 64     for (int i=1;i<list[0];++i)
 65     {
 66         memset(P,0,sizeof(P)),len=1;
 67         sum=Calc(1,N,list[i],list[i+1]-1);
 68         memcpy(Ptmp,P,sizeof(P));
 69         lentmp=len;
 70         for (int j=list[i];j<list[i+1];++j)
 71         if (A[j]!=A[j-1])
 72         {
 73             len=lentmp;
 74             memcpy(P,Ptmp,sizeof(Ptmp));
 75             tmp=Calc(list[i],list[i+1]-1,j,j);
 76             if (tmp>Ret)    ret=j,Ret=tmp;
 77         }
 78     }
 79     printf("%d ",A[ret]);
 80     memset(P,0,sizeof(P)),len=1;
 81     Calc(1,N,ret,ret);
 82     for (int i=1;i<=len;++i)
 83     for (int j=P[i].x;j<=P[i].y;++j)
 84         S[j]=1;
 85     for (int i=1;i<=1400000;++i)
 86         S[i]+=S[i-1];
 87     ++len;
 88     P[len].x=P[len-1].y+2;
 89     P[len].y=1<<30;
 90     for (int i=1;i<len;++i)
 91     {
 92         bool mk=0;
 93         for (int j=P[i].y+1;j<P[i+1].x;++j)
 94         if (check(j))  
 95         {
 96             ret=j;mk=1;break;
 97         }
 98         if (mk)    break;
 99     }
100     printf("%d\n",ret);
101     return 0;
102 }
103 

posted on 2010-05-21 15:10 jsn1993 阅读(1762) 评论(2)  编辑 收藏 引用 所属分类: Mix

评论

# re: 【除草】Baltic OI 2010 day2 candies 2010-06-30 09:42 jiakai

b[1], b[2], ..., b[i]分别为2^i,后面的都取7000, 则所有偶数都可以组合出来,奇数都不可组合出来,区间数是O(n)级别的,没有优化效果。。  回复  更多评论   

# re: 【除草】Baltic OI 2010 day2 candies 2010-06-30 09:57 jsn1993

@jiakai
对 这是个人品算法 所以求标准算法  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理