题目链接 HDU6149
百度之星复赛的题目……比赛的时候并没有做出来。
由于低点只有15个,所以我们可以考虑状压DP。
利用01背包的思想,依次考虑每个低点,然后枚举每个状态。
在每个状态里面任意枚举不在这个状态中的两个点,如果能构成一个valley,那么更新答案。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL; const int N = 53; int dp[2][(1 << 15) + 20];
int a[N], f[N], mp[N][N];
int n, m, q;
int T, x, y, S, now, ret; int main(){ scanf("%d", &T);
while (T--){
scanf("%d%d%d", &n, &m, &q);
memset(dp, 0, sizeof dp);
memset(mp, 0, sizeof mp);
memset(f, 0, sizeof f); rep(i, 1, m){
scanf("%d%d", &x, &y);
mp[x][y] = mp[y][x] = 1;
} rep(i, 0, q - 1){
scanf("%d", a + i);
f[a[i]] = 1;
} S = (1 << q) - 1;
now = 0;
rep(i, 1, n){
if (f[i]) continue;
now ^= 1;
rep(j, 0, S) dp[now][j] = dp[now ^ 1][j];
rep(j, 0, S){
rep(k, 0, q - 1){
if (!(j & (1 << k)) && mp[i][a[k]]){
rep(l, k + 1, q - 1){
if (!(j & (1 << l)) && mp[i][a[l]]){
int st = j | (1 << k) | (1 << l);
dp[now][st] = max(dp[now][st], dp[now ^ 1][j] + 1);
}
}
}
}
}
} ret = 0;
rep(i, 0, S) ret = max(ret, dp[now][i]);
printf("%d\n", ret);
} return 0;
}