很久沒寫了。。。
題意：
給你一個裝箱問題(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