首页 > 代码库 > hdu_5890_Eighty seven(bitset优化DP)

hdu_5890_Eighty seven(bitset优化DP)

题目链接:hdu_5890_Eighty seven

题意:

50个数,10W个询问,每次问删掉第i,j,k个数后,是否存在一种选10个数和为87的方案,只需要输出 ’Yes’ 或者 ’No’

题解:

暴力:不同的询问大概2W个,每个暴力bitset DP,抠一抠能卡着过。优化1:先求出一组解,如果询问和解没交就是’Yes’,否则暴力,不同的询问大概1W个;优化2:先预处理出所有询问的答案,能方便的复用之前的DP数组,不用每次从头开始重新求。

以上是camp的题解

这里学习了一下bitset,把87*n优化到了10*n,然后可以卡过去

dp[i][j]表示选了i个数和为j的情况,dp[j]|=dp[j-1]<<a[i],j从10到1,这样就能优美的记录和的情况

技术分享
 1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4  5 bitset<90>dp[11]; 6 int ans[55][55][55],a[55],n,m,q[4],T; 7  8 bool check(int x,int y,int z) 9 {10     F(i,0,10)dp[i].reset();11     dp[0][0]=1;12     F(i,1,n)if(i!=x&&i!=y&&i!=z)for(int j=10;j>0;j--)dp[j]|=dp[j-1]<<a[i];13     return dp[10][87];14 }15 16 int main()17 {18     scanf("%d",&T);19     while(T--)20     {21         memset(ans,0,sizeof(ans));22         scanf("%d",&n);23         F(i,1,n)scanf("%d",a+i);24         F(i,1,n)F(j,i,n)F(k,j,n)if(check(i,j,k))ans[i][j][k]=1;25         scanf("%d",&m);26         while(m--)27         {28             F(i,0,2)scanf("%d",q+i);29             sort(q,q+3);30             if(ans[q[0]][q[1]][q[2]])puts("Yes");else puts("No");31         }32     }33     return 0;34 }
View Code

 

hdu_5890_Eighty seven(bitset优化DP)