abc288g

通过这道题复习一下sosdp。

sosdp用于求解子集和。

我们设\(f[i][s]\)表示后\(i\)位是\(s\)的子集，前\(n-i\)位等于\(s\)的\(a\)中的数的和

在从\(f[i][s]\)转移到\(f[i+1]\)时，需要分2种情况讨论。

1.当\(s\)的第\(i+1\)位是\(1\)，\(f[i+1][s]=f[i][s]+f[i][s xor 2^i]\)

2.当\(s\)的第\(i+1\)位是\(1\)，\(f[i+1][s]=f[i][s]\)

这道题事实上可以类似sosdp，然后把这个过程反着做。

#include<bits/stdc++.h>

using namespace std;

int n,a[1000000],pw[1000],f[1000000][15];

int main(){

	pw[0]=1;

	for(int i=1;i<14;i++)

		pw[i]=pw[i-1]*3;

	scanf("%d",&n);

	for(int i=0;i<pw[n];i++)

		scanf("%d",&a[i]);

	for(int i=0;i<pw[n];i++)

		f[i][0]=a[i];

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

		for(int j=0;j<pw[n];j++){

			int wz=(j/pw[i])%3;

			int pz=wz*pw[i];

			int p1=f[j-pz][i],p2=f[j-pz+pw[i]][i],p3=f[j-pz+pw[i]*2][i];

			if(wz==0)

				f[j][i+1]=p2-p3;

			else if(wz==1)

				f[j][i+1]=p3+p1-p2;

			else

				f[j][i+1]=p2-p1;

		}

	for(int i=0;i<pw[n];i++)

		printf("%d ",f[i][n]);

}

巴特西

abc288g

最新文章

热门文章