bzoj4976(dp+思维)

xiaoxiao2021-02-28  16

题目链接: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; } 
转载请注明原文地址: https://www.6miu.com/read-1650026.html

最新回复(0)