很久沒寫了。。。
題意：
給你一個(gè)裝箱問題(N<=100 Ai<=7000) 記用這些有限物品能拼成的重量種數(shù)為Ans
求 把i物品Ai 換成X后 使新的能得到的重量種數(shù)Ret最大 同時(shí)使X最小 求X和Ret
做法：
這個(gè)題我做了一晚上加一上午！！
猜想：
換一個(gè)物品 等價(jià)于 先去掉這個(gè)物品做N-1個(gè)物品 最后加入一個(gè)物品并更新
（寫了個(gè)暴力 是符合的）
然后就將問題變?yōu)榱苏嬲膬蓡枺?br>第一問，求X使得除了X的N-1個(gè)物品能得到的種數(shù)Ans'最大
（因?yàn)樽罱K方案一樣 所以得刪一個(gè)最沒用的）
第二問，添加一個(gè)物品 使得最后得到的最大
對(duì)于第一問 一個(gè)簡(jiǎn)單的想法便是枚舉去掉哪個(gè)物品 做100次裝箱問題
但是我們還是遇到了瓶頸 做一次裝箱問題復(fù)雜度O(100^2*7000) 枚舉的話 做一次就得0.5秒 根本無(wú)法滿足
（很不幸我想不到不枚舉的方法 只能用區(qū)間背包這個(gè)不好估計(jì)復(fù)雜度的來完成 實(shí)際效果確實(shí)還得TLE）
【我的做法便是將100個(gè)物品分為10組 枚舉每10個(gè)物品 先將另外90個(gè)物品做好區(qū)間背包 保存這個(gè)答案數(shù)組然后對(duì)于這10個(gè)物品 每次添加9個(gè)物品算下復(fù)雜度原本要放進(jìn)99*100=9900次物品現(xiàn)在 90*10+9*9*10=2000次左右 整整減少了5倍！】
對(duì)于第二問 事實(shí)上我們可以發(fā)現(xiàn) 添加Y=(∑Ai)-X+1這個(gè)物品是肯定可以將方案數(shù)增加最多的 因?yàn)?br>假設(shè)用N-1個(gè)物品能得到的裝箱數(shù)組是
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必然是一個(gè)使方案最大可行解 亦可能是最優(yōu)解
所以我們?nèi)绻乙粋€(gè)比Y更優(yōu)的解 必然要滿足原本擁有的所有解加上Y' 原本都不可行！
這樣就把問題轉(zhuǎn)化為如下：
對(duì)于一個(gè)1..700000的布爾數(shù)組A 求一個(gè)最小的X
使得對(duì)于任意一個(gè)i A[i]=1 A[i+X]=0。
（很不幸除了枚舉X 這一問我也不會(huì)做 ）
【我的做法
先預(yù)處理前綴和 即從1開始到i能拼成的個(gè)數(shù)
先把這個(gè)枚舉加些剪枝 將原來拼不成的重量進(jìn)行枚舉
再?gòu)倪@些拼不成的重量里枚舉X 因?yàn)閰^(qū)間背包算出來的是許多個(gè)區(qū)間 最后枚舉這些區(qū)間
對(duì)于一個(gè)區(qū)間[a,b] 如果X是可行的那必然有 sum(a+X,b+X)=0】
事實(shí)上這么做居然就過了！因?yàn)閰^(qū)間數(shù)不太多 我能構(gòu)造的最牛逼的數(shù)據(jù) 也只能 O(300000*5000) 這個(gè)還是勉強(qiáng)能跑過的
對(duì)于官方數(shù)據(jù) 每個(gè)點(diǎn)都能在0.2s內(nèi)跑過！！
這樣終于AC了此題！！
（另外求標(biāo)準(zhǔn)的優(yōu)美的算法!!!!!!!!!）
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