Jumping Takahashi （DFS剪枝）

原题：https://atcoder.jp/contests/abc240/tasks/abc240_c

题意：x初始为0，每一步(第i步)可以选择增加a[i]或b[i]，问n步后x能否到达X

dfs剪枝过，不剪枝应该会t

按层搜的bfs应该更快，懒得写队列

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <time.h>
#include <iomanip>
#include <cctype>
#include <string>
using namespace std;
typedef long long ll;
const ll Mod = 1e9 + 7;     //https://atcoder.jp/contests/abc240/tasks/abc240_c
//剪枝策略：
//1.超过X就return
//2.同一层当前值相同且已经搜过就return，用bool类型vis[层数][值]表示是否搜过
//3.搜到一组可行方案就结束整个dfs，用isdone标记
int a[110],b[110];
bool vis[110][10010];
int N,X;
bool ans;
bool isdone;
void dfs(int n,int x){
    if(isdone) return ;    //找到了就不用搜了
    if(vis[n][x]) return ; //搜过就不用搜了
    if(x>X) return ;       //超过X就不用搜了
    if(n==N+1&&x==X){      //搜完n层达到X就出true并标记，整个dfs结束
        ans=true;
        isdone=true;
        return ;
    }
    else if(n==N+1)
        return ;
    dfs(n+1,x+a[n]);
    vis[n+1][x+a[n]]=true;
    dfs(n+1,x+b[n]);
    vis[n+1][x+b[n]]=true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin>>N>>X;
    for(int i=1;i<=N;i++){
        cin>>a[i]>>b[i];
    }
    
    dfs(1,0);
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}