[TC14860]SquadConstructor2

题目大意：

有\(n(n<2^m,m\le8)\)个互不相等的数\(v_i\)。从中选取\(k(k\le8)\)个数\(b_i\)，求\(\sum_{i=0}^m(\sum_{j=1}^k[b_j\wedge 2^i=2^i])^2\)的最大值。

思路：

一个显然的动态规划\(f[i][s]\)表示选择了\(i\)个数，是否能使得状态为\(s\)。其中状态\(s\)表示\(0\sim m-1\)中每一个二进制位出现次数。显然可以做到\(\mathcal O(n\cdot k\cdot9^m)\)。使用bitset优化，做到\(\mathcal O(\frac{n\cdot k\cdot9^m}\omega)\)。

源代码：

#include<vector>

#include<bitset>

constexpr int M=8,N=1<<M,K=9;

constexpr int pwr[]={1,9,81,729,6561,59049,531441,4782969,43046721};

class SquadConstructor2 {

	private:

		int b[N];

		std::bitset<pwr[M]> f[K];

		int sqr(const int &x) const {

			return x*x;

		}

	public:

		int teamget(const int &m,const int &k,std::vector<int> v) {

			const int n=v.size();

			for(register int i=0;i<n;i++) {

				for(register int j=0;j<m;j++) {

					if(v[i]&(1<<j)) b[i]+=pwr[j];

				}

			}

			f[0][0]=1;

			for(register int i=0;i<n;i++) {

				for(register int j=k;j;j--) {

					f[j]|=f[j-1]<<b[i];

				}

			}

			int ans=0;

			for(register int s=0;s<pwr[m];s++) {

				if(!f[k][s]) continue;

				int tmp=0;

				for(register int i=0;i<m;i++) {

					tmp+=sqr(s/pwr[i]%9);

				}

				ans=std::max(ans,tmp);

			}

			return ans;

		}

};