bzoj4976(dp+思维)

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4976 题意：中文题目就不说了吧！ 思路：最初是真没想到dp，可能思维太僵化了吧。其实细想一下，有这样一个条件，就是说n-k>=16，那么二进制位 每位都是1，直接计算出即可。这里为什么是16呢，二进制位0-16求一个等比数列和再和1e5 比较就知道了。因为这 里 k小于等于100，也就是说n小于等于116，以dp[i][j]表示前i项或和为j最多可以去掉数的个数。转移见代码。 #include<bits/stdc++.h> using namespace std; const int maxn = 1 << 17; const int maxm = 1e5 + 5; int dp[120][maxn]; int a[maxm]; int main() {     int n, k;     while(scanf("%d%d", &n, &k) != EOF)     {         int ans = 0;         memset(dp, -n, sizeof(dp));         for(int i = 1; i <= n; i++)         {             scanf("%d", &a[i]);             ans |= a[i];         }         if(n - k >= 16)         {             printf("%d\n", ans);             continue;         }         ans = 0;         dp[0][0] = 0;         for(int i = 1; i <= n; i++)         {             for(int j = 0; j < maxn; j++)             {                 dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);                 dp[i][j | a[i]] = max(dp[i][j | a[i]], dp[i - 1][j]);             }         }         for(int i = 1; i < maxn; i++)         {             if(dp[n][i] >= k) ans = i;         }         printf("%d\n", ans);     }     return 0; }