hdu 6140 Hybrid Crystals 阅读题 OR bitset 优化01背包

题目连接

题意:

确实比较坑,题中给出的信息保证了凑出的数连续,

但是我一直以为没什么用也没发现这个....然后就发现01背包肯定T了啊,那我就bitset优化一下吧.第一次写bitset,没办法 xjb搞搞吧,然后就一直T.

这里bitset优化的时间复杂度大致是n*k/64  或者/32 吧 这个不太清楚.

如果这个是个搜索我肯定就想到了这种剪枝...但是没想到...这样优化的常数是巨大的.

就是当所有负数加起来的和 大于k,或者所有正数加起来的和小于k.那么肯定就凑不出来了啊...这时候就不需要去跑背包了,节省了常数...

另外我把所有N,都double了一下...这种方法不太提倡吧,毕竟不是正解。。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn = 2e6 + 7 ;
const int maxm = 2e3 + 7;
int a[maxm], num[maxm];
bitset<maxn> dp;
char b;

inline int read(){
    int x=0,f=1;char ch = getchar();
    for(;ch<'0'||'9'<ch;ch=getchar())if(ch=='-') f=-1;
    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}


int main()
{
    int n, k, t;
    scanf("%d", &t);
    while(t--)
    {
        dp.reset();
        scanf("%d%d", &n, &k);
        // k += maxm;
        for(int i = 1; i <= n; i++)
            a[i] = read();
        int tot = 1;
        for(int i = 1; i <= n; i++)
        {
            scanf(" %c", &b);
            if(b == 'L')
                num[tot++] = a[i];// num[tot-1] += maxm;
            else if(b == 'D')
                num[tot++] = -a[i];//num[tot-1] += maxm;
            else
            {
                num[tot++] = a[i];// num[tot-1] += maxm;
                num[tot++] = -a[i];//num[tot-1] += maxm;
            }
        }
        int sum1=0,sum2=0;  
        for(int i=1;i < tot;++i){  
            if(num[i] < 0) sum2 += num[i];  
            if(num[i] > 0) sum1 += num[i];  
        }  
        
        
        
        if(sum2>k||sum1<k) //最最重要的剪枝 
        {
        	puts("no");
        	continue;
        }
		k += 1e6;
		dp.set(1e6);
        for(int i = 1; i < tot; i++)
        {
            if(dp.test(k))//一点小优化, 无影响. 
            break;
            if(num[i] > 0)
            {
                dp |= (dp << num[i]);
            }
            else
            {
                num[i] = -num[i];
                dp |= (dp >> num[i]);
            }
        }

        //k += 1e6;
        if(dp.test(k))
            puts("yes");
        else
        {
            puts("no");
        }
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e3+10;
int a[maxn];
char b[maxn][2];
int n,k;
int main()
{
	int _;
	cin>>_;
	while(_--)
	{
		cin >> n >> k;
		for(int i = 1;i <= n;i++)
		scanf("%d",&a[i]);
		for(int i = 1;i <= n;i++)
		scanf("%s",b[i]);
		int l = 0,r = 0;
		for(int i = 1;i <= n;i++)
		{
			if(b[i][0] != 'L')
			l -= a[i];
			if(b[i][0] != 'D')
			r += a[i];
		}
		if(l <= k && k <= r)
		puts("yes");
		else
		puts("no");
	}
	return 0;
}