HDU 6140 Hybrid Crystals(思考+上下界)

题意

有n个水晶，水晶有N D L 三种属性代表能量的正负，并且每个水晶都有能量，N是可正可负，D是负，L是正，问取一些水晶，能否使能量值达到k

并且题意保证：
第一个水晶一定是能量为1的N水晶
每一个水晶的能量一定小于前面同属性的+N属性的能量值。

思路

这题最重要的还是运用那个保证条件。

假设一个水晶的能量为 x ，之前的集合中已经可以达到 [−a,b] 这个区间中的数，
如果它是L水晶，那么当 x 加入这个集合，因为集合内的右区间 b 一定是大于 x 的，因此这时右边界的 [b,b+x] 也是可达的，（因为之前就是连续的区间可达），因此对于整个集合来说， [−a,b+x] 可达。
如果是D水晶，因为左区间 a 一定是大于 x 的，因此左边界变为 [−a−x,b]
如果是N水晶，无论左右区间都可以因x改变，所以变为 [−a−x,b+x]

就是题意不会给你出不连续的水晶点，像
1 4
N L
这种样例都是不存在的。。。。。
大坑

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
const int N = 2E3+10;
int a[N];
char s[N];
int bfs(){

}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, k;
        int l, r;
        scanf("%d %d",&n, &k);
        int x;
        for(int i = 1; i <= n; i++){
            scanf("%d", &x);
            a[i] = x;
        }
        int flag = 0;
        for(int i = 1; i <= n; i++){
            scanf("%s", s);

            if(flag) continue;
            if(i == 1){
                l = -1;
                r = 1;
            }

            else if(s[0] == 'L'){
                r += a[i];
            }
            else if(s[0] == 'D'){
                l -= a[i];
            }
            else if(s[0] == 'N'){
                l -= a[i];
                r += a[i];
            }

            if(k <= r && k >= l){
                flag = 1;
            }


        }

        if(flag) puts("yes");
        else puts("no");



    }
}