hdu 6140 Hybrid Crystals 思维

http://acm.hdu.edu.cn/showproblem.php?pid=6140

有n个物体，每个物体有一个权值，问能否选择部分物体使得组成的权值为k

每个物体有不同类型，L：权值为正，D：权值为负，N：权值可正可负

并且a1=1，类型为N，ai<sum(类型为N和和自己同类型的物体权值aj)  且j<i

因为a1=1，类型为N，通过a1可以得到-1，0，1的状态，而有了“ai<sum(类型为N和和自己同类型的物体权值aj)  且j<i”这个条件，每次都可以得到连续的可行的状态

最后判一下就可以了

#include<bits/stdc++.h>
using namespace std;
int a[1005];
char b[1005];
int main()
{
    int T,n,k,i,j;
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<n;i++)
        {
            scanf(" %c",&b[i]);
        }
        int le=-1,ri=1;
        for(i=1;i<n;i++)
        {
            if(b[i]!='D')
            {
                ri+=a[i];
            }
            if(b[i]!='L')
            {
                le-=a[i];
            }
        }
        if(k<=ri&&k>=le)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

利用一个后缀优化一下背包的范围。。。。500+ms卡过

和正解差距太大

#include<bits/stdc++.h>
using namespace std;
int dp[2000505];
int a[1005];
char b[1005];
int minn[1005],maxx[1005];
int pian=1000010;
int main()
{
    int T,n,k,i,j;
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<n;i++)
        {
            scanf(" %c",&b[i]);
        }
        if(k<0)
        {
            for(i=0;i<n;i++)
            {
                if(b[i]=='D')
                    b[i]='L';
                else if(b[i]=='L')
                    b[i]='D';
            }
            k*=-1;
        }
        for(i=n-1;i>=0;i--)
        {
            minn[i]=minn[i+1];
            maxx[i]=maxx[i+1];
            if(b[i]=='N'||b[i]=='L')
                minn[i]+=a[i];
            else if(b[i]=='N'||b[i]=='D')
                maxx[i]+=a[i];
        }
        memset(dp,0,sizeof(dp));
        int sum1=pian,sum2=pian;
        dp[pian]=1;
        for(i=0;i<n;i++)
        {
            if(b[i]=='N'||b[i]=='L')
            {
                int down=sum1+a[i],up=sum2+a[i];
                for(j=up;j>=down;j--)
                {
                    dp[j]|=dp[j-a[i]];
                }
                sum2+=a[i];
                if(sum2>=k+pian+maxx[i])
                    sum2=k+pian+maxx[i];
            }
            if(b[i]=='N'||b[i]=='D')
            {
                int down=sum1-a[i],up=sum2-a[i];
                for(j=down;j<=up;j++)
                {
                    dp[j]|=dp[j+a[i]];
                }
                sum1-=a[i];
                if(sum1<k-minn[i]+pian)
                sum1=k-minn[i]+pian;
            }
        }
        if(dp[k+pian])
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}