\u5176\u4e2d\uff0c\\(f[k]\\)\u8868\u793a\u9012\u63a8\u5230\u7b2ci\u4f4d\u7684\u6700\u5927\u503c\u3002
\n\u90a3\u4e48\uff0c\\(f[k]\\)\u663e\u7136\u662f\u53ef\u4ee5\u4ece\\(f[k-1]\\)\u9012\u63a8\u6765\u7684\u3002
\n\u8fd9\u65f6\u5019\u53ea\u8981\u8003\u8651\\(i|j==k\\)\u7684\u503c\u3002
\n\u679a\u4e3ek\u7684\u5b50\u96c6\uff0c\u6c42\u6700\u5927\u503c\u3002
\n\u8fd9\u6837\u505a\u662f\\(O(\u677e\u677e\u677e)\\)\u7684\u3002
\n\u8003\u8651\u4f18\u5316\u3002
\n\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u5bf9\u4e8ek\u7684\u6bcf\u4e00\u4e2a\u5b50\u96c6\uff0c\u5b83\u7684\u5b50\u96c6\u7684\u6700\u5927\u503c\u662f\u5df2\u7ecf\u6c42\u8fc7\u7684\u3002
\n\u90a3\u4e48\u6211\u4eec\u53ea\u9700\u8981\u8003\u8651\u679a\u4e3e\u6bcf\u4e00\u4e2ak\u5b50\u96c6\u7684\u4e00\u90e8\u5206\uff0c\u53ef\u4ee5\u8003\u8651\u6bcf\u4e00\u6b21\u628a\u5b83\u53cd\u4e0e\u4e0a\u4e00\u4e2a\\(2^l\\)\uff0c\u5e76\u6c42Max\u548c\u6b21Max\u3002
\n\u8fd9\u6837\u6709\u89e3\uff0c\u590d\u6742\u5ea6\\(O(n*2^n)\\)\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))\r\n#define Swap(_A,_B) ((_A)^=(_B)^=(_A)^=(_B))\r\nusing namespace std;\r\n\/\/mx[i][0]\u8868\u793a\u6700\u5927\u503c\uff0cmx[i][1]\u8868\u793a\u6b21\u5927\u503c\u3002 \r\nint f[1<<18],n,a[1<<18];\r\nint nw,mxx,lmxx,sa,sb,st;\r\nstruct data{\r\n int v;\r\n int nm;\r\n bool operator ==(const data &x)const{\r\n return this->v==x.v&&this->nm==x.nm;\r\n }\r\n}lst[40],mx[1<<18][2];\r\ninline bool cmp(const data &x,const data &y){\r\n return x.v>y.v;\r\n}\r\n\/\/\u5904\u7406\u7b2ck\u4e2a\u6570\uff0c\u5b83\u7684\u6700\u5927\u503c\u548c\u6b21\u5927\u503c\u3002 \r\nint wrk(int k){\r\n nw=0,mxx=0,lmxx=0,sa=-1,sb=-1,st=0;\r\n lst[++st]=(data){a[k],k};\r\n for(int i=0;(1<<i)<=k;++i){\r\n if((k>>i)&1){\r\n nw=k^(1<<i);\r\n }else{\r\n continue;\r\n }\r\n lst[++st]=mx[nw][0];\r\n lst[++st]=mx[nw][1];\r\n }\r\n sort(lst+1,lst+1+st,cmp);\r\n unique(lst+1,lst+1+st);\r\n mx[k][0]=lst[1],mx[k][1]=lst[2];\r\n return mx[k][0].v+mx[k][1].v;\r\n}\r\nvoid init(){\r\n scanf(\"%d\",&n);\r\n const int MAX=1<<n;\r\n for(int i=0;i<MAX;++i){\r\n scanf(\"%d\",&a[i]);\r\n }\r\n f[0]=0,mx[0][0].v=a[0],mx[0][1].v=0,mx[0][0].nm=0,mx[0][1].nm=-1;\r\n for(int k=1;k<MAX;++k){\r\n f[k]=wrk(k);\r\n f[k]=Max(f[k],f[k-1]);\r\n printf(\"%d\\n\",f[k]);\r\n }\r\n}\r\nint main(){\r\n init();\r\n return 0;\r\n} <\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5176\u4e2d\uff0c\\(f[k]\\)\u8868\u793a\u9012\u63a8\u5230\u7b2ci\u4f4d\u7684\u6700\u5927\u503c\u3002 \u90a3\u4e48\uff0c\\(f[k]\\)\u663e\u7136\u662f\u53ef\u4ee5\u4ece\\(f[k-1]\\)\u9012\u63a8\u6765 … <\/p>\n