Hybrid Crystals

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 323    Accepted Submission(s): 192


Problem Description > Kyber crystals, also called the living crystal or simply the kyber, and known as kaiburr crystals in ancient times, were rare, Force-attuned crystals that grew in nature and were found on scattered planets across the galaxy. They were used by the Jedi and the Sith in the construction of their lightsabers. As part of Jedi training, younglings were sent to the Crystal Caves of the ice planet of Ilum to mine crystals in order to construct their own lightsabers. The crystal's mix of unique lustre was called "the water of the kyber" by the Jedi. There were also larger, rarer crystals of great power and that, according to legends, were used at the heart of ancient superweapons by the Sith.
>
> — Wookieepedia

Powerful, the Kyber crystals are. Even more powerful, the Kyber crystals get combined together. Powered by the Kyber crystals, the main weapon of the Death Star is, having the firepower of thousands of Star Destroyers.

Combining Kyber crystals is not an easy task. The combination should have a specific level of energy to be stablized. Your task is to develop a Droid program to combine Kyber crystals.

Each crystal has its level of energy ( i -th crystal has an energy level of ai ). Each crystal is attuned to a particular side of the force, either the Light or the Dark. Light crystals emit positive energies, while dark crystals emit negative energies. In particular,

* For a light-side crystal of energy level ai , it emits +ai units of energy.
* For a dark-side crystal of energy level ai , it emits −ai units of energy.

Surprisingly, there are rare neutral crystals that can be tuned to either dark or light side. Once used, it emits either +ai or −ai units of energy, depending on which side it has been tuned to.

Given n crystals' energy levels ai and types bi ( 1≤i≤n ), bi=N means the i -th crystal is a neutral one, bi=L means a Light one, and bi=D means a Dark one. The Jedi Council asked you to choose some crystals to form a larger hybrid crystal. To make sure it is stable, the final energy level (the sum of the energy emission of all chosen crystals) of the hybrid crystal must be exactly k .

Considering the NP-Hardness of this problem, the Jedi Council puts some additional constraints to the array such that the problem is greatly simplified.

First, the Council puts a special crystal of a1=1,b1=N .

Second, the Council has arranged the other n−1 crystals in a way that
ai≤∑j=1i−1aj[bj=N]+∑j=1i−1aj[bi=L∩bj=L]+∑j=1i−1aj[bi=D∩bj=D](2≤i≤n).
[cond] evaluates to 1 if cond holds, otherwise it evaluates to 0 .

For those who do not have the patience to read the problem statements, the problem asks you to find whether there exists a set S⊆{1,2,…,n} and values si for all i∈S such that

∑i∈Sai∗si=k,

where si=1 if the i -th crystal is a Light one, si=−1 if the i -th crystal is a Dark one, and si∈{−1,1} if the i -th crystal is a neutral one.  
Input The first line of the input contains an integer T , denoting the number of test cases.

For each test case, the first line contains two integers n ( 1≤n≤103 ) and k ( |k|≤106 ).

The next line contains n integer a1,a2,...,an ( 0≤ai≤103 ).

The next line contains n character b1,b2,...,bn ( bi∈{L,D,N} ).  
Output If there exists such a subset, output "yes", otherwise output "no".  
Sample Input

  
  
   
   2

5 9 
1 1 2 3 4
N N N N N 

6 -10
1 0 1 2 3 1
N L L L L D
  
  

 
Sample Output

  
  
   
   yes
no
  
  

题目大意：

有三种物品，L,D,N，L是光明属性，D是黑暗属性，N是中性。光明属性贡献的价值是正的，黑暗属性贡献的价值是负的，中性可以正可以负，我们任意设定，问我们能否从中选择一些物品，使得贡献值总和为K，保证a1=1，b1=N；还有一个保证在题干给出了，式子太长不描述了。

思路：

http://gdutcode.sinaapp.com/problem.php?cid=1056&pid=7

这个题和这个题基本一样。

如果我们能够组成区间【1~sum】之内所有的数的话，如果我们现在有一个新的数x加入，并且有：x<=sum+1的话，那么我们接下来就能够凑出来【1~sum+x】的数。

这个题同理，满足了题干描述的那个条件之后，我们其实就可以直接将其加入进去。

如果是L类型的，那么可以凑成的答案区间就能够变成【L,R+Ai】；

同理，如果是N类型的，那么可以凑成的答案区间就能够变成【L-Ai,R+Ai】；

再同理，如果是D类型的，那么可以凑成的答案区间就能够变成【L-Ai,R】；

依次类推，然后最终判一下就行了。

Ac代码：

#include<stdio.h>
#include<string.h>
using namespace std;
int a[150000];
char b[150000][3];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        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;
        int R=0;
        for(int i=1;i<=n;i++)
        {
            if(b[i][0]=='L')
            {
                R+=a[i];
            }
            else if(b[i][0]=='D')
            {
                L-=a[i];
            }
            else
            {
                L-=a[i];
                R+=a[i];
            }
        }
        if(m>=L&&m<=R)printf("yes\n");
        else printf("no\n");
    }
}