[JZOJ] 5935. 小凯学数学

由Noip2018初赛的知识得，a|b + a&b = a+b

设计一个区间dp，设\(f[l][r][x]\)表示区间\([l,r]\)能否构成\(x\)，数据不大，转移暴力枚举

复杂度\(O(n^3\times MAXN^3)\)

#include<algorithm>

#include<iostream>

#include<cstdio>

using namespace std;

inline int rd(){

  int ret=0,f=1;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

  while(isdigit(c))ret=ret*10+c-'0',c=getchar();

  return ret*f;

}

#define space() putchar(' ')

#define nextline() putchar('\n')

void pot(int x){if(!x)return;pot(x/10);putchar('0'+x%10);}

void out(int x){if(!x)putchar('0');if(x<0)putchar('-'),x=-x;pot(x);}

const int MAXN = 155;

bool f[MAXN][MAXN][8];

int n;

int main(){

	n=rd();

	for(int i=1;i<=n;i++)f[i][i][rd()]=1;

	for(int len=2;len<=n;len++){

		for(int i=1;i+len-1<=n;i++){

			int j=i+len-1;

			for(int k=i;k<j;k++){

				for(int x=0;x<=7;x++){

					for(int y=0;y<=7;y++){

						for(int z=0;z<=7;z++){

							if(((y+z)>>1)!=x)continue;

							f[i][j][x]|=f[i][k][y]&f[k+1][j][z];

						}

					}

				}

			}

		}

	}

	for(int i=0;i<=7;i++) if(f[1][n][i]) out(i),space();

	return 0;

}

巴特西

[JZOJ] 5935. 小凯学数学

最新文章

热门文章