首页 > 代码库 > HDU 5890 Eighty seven(DP+bitset优化)
HDU 5890 Eighty seven(DP+bitset优化)
这个题的背包的思想还是很容易想到的,但是这个bitset优化还是有点神奇的呀。。
#include<bitset> #include<stdio.h> #include<string.h> #include<iostream> #include<map> #include<algorithm> using namespace std; bitset<90>A[11]; const int maxn=1e3; int n,a[maxn]; int dp[52][52][52]; int vaild(int x,int y,int z) { for(int i=0;i<=10;i++) A[i].reset(); A[0][0]=1; for(int i=1;i<=n;i++) { if(i!=x&&i!=y&&i!=z&&a[i]<=87) { for(int j=10;j>=1;j--) { A[j]|=(A[j-1]<<a[i]); } } }if(A[10][87]) return 1; return 0; } /* int vaild(int i,int j,int k) { for (int h=0;h<=10;h++) A[h].reset();A[0][0]=1; for (int h=1;h<=n;h++) if (h!=i&&h!=j&&h!=k&&a[h]<=87) { for (int ii=9;ii>=0;ii--) A[ii+1]|=A[ii]<<a[h]; if (A[10][87]) return 1; } return 0; }*/ int main() { int T; scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { for(int k=j;k<=n;k++) { dp[i][j][k]=vaild(i,j,k); } } } int q; scanf("%d",&q); while(q--) { int b[4]; scanf("%d%d%d",&b[1],&b[2],&b[3]); sort(b+1,b+4); if(dp[b[1]][b[2]][b[3]]) printf("Yes\n"); else printf("No\n"); } } }
HDU 5890 Eighty seven(DP+bitset优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。