zufe 问题 : Sometimes Naive

zufe 问题 : Sometimes Naive"/>

zufe 问题 : Sometimes Naive

这道题比较难，状压dp，再加两个预处理

#include<bits/stdc++.h>using namespace std;const int maxn = (1 << 20) + 10;
int a[22],n;bool dp[maxn];
vector<int> g[maxn];
int len[maxn];
int p[maxn], sz;int t[maxn];int lowbit(int x) {return x & (-x);
}void init()
{for(int i = 0 ; i < sz ; i ++){int temp = p[i];int x[3], cnt = 0;while(temp) {int h = lowbit(temp);x[cnt ++] = t[h];temp -= h;}x[0] = a[n - x[0] - 1];x[1] = a[n - x[1] - 1];x[2] = a[n - x[2] - 1];sort(x, x + 3);if(x[0] > x[2] - x[1])dp[p[i]] = 1;}
}void f() {for(int i = 0 ; i < 20; i ++) {t[1 << i] = i;}for(int i = 1; i < maxn; i ++){len[i] = len[i - lowbit(i)] + 1;if(len[i] == 3){p[sz ++] = i;}}int sum = 0;for(int i = 0; i < (1 << 20); i ++){if(len[i] % 3 != 0)continue;for(int j = 0; j < sz; j ++){if((i & p[j]) != 0)continue;g[i].push_back(p[j]);}sum = sum + g[i].size();}// cout << sum << endl;
}int main()
{f();// cout << "ok" << endl;//  cout << p[0] << endl;int T;scanf("%d",&T);for(int u = 1; u <= T; u ++){memset(dp, 0, sizeof(dp));int ma = 0;scanf("%d",&n);for(int i = 0; i < n ; i ++)scanf("%d",&a[i]);init();dp[0] = 1;for(int S = 0; S < (1 << n); S ++){if(dp[S] == 0)continue;for(int j = 0; j < g[S].size(); j ++){if(dp[g[S][j]] && S + g[S][j] < (1 << n))dp[S + g[S][j]] = 1;}}for(int i = 0 ; i < (1 << n); i ++){if(dp[i] == 1){ma = max(ma, len[i] / 3);}}printf("Case #%d: ",u);printf("%d\n",ma);}return 0;
}