很久没写了。。。
题意：
给你一个装箱问题(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