微众银行2024.3.31笔试-动态规划

#include<bits/stdc++.h>
using namespace std;
int dp[1000][2]; // 定义一个二维数组dp，用于存储动态规划的结果
int x,s,a,b,c,d; // 定义一些整型变量

// 定义一个递归函数solve，用于求解问题
int solve(int x,int delta, int side)
{
    if(x>=delta) // 如果x大于等于delta，说明已经到达目标位置，返回side^1（side的异或值）
    {
        dp[delta][0] = dp[delta][1] = side^1;
        return side^1;
    }
    if(dp[x][side]!=-1)return dp[x][side]; // 如果dp[x][side]不等于-1，说明已经计算过，直接返回结果
    if(side) // 如果side为真，表示当前在a到b的范围内
    {
        for(int i=a;i<=b;i++) // 遍历a到b的范围
        {
            if(solve(x+i, delta, side^1) == side)return dp[x][side]=side; // 如果递归调用solve函数返回的结果等于side，说明找到了解决方案，返回side
        }
    }
    else // 如果side为假，表示当前在c到d的范围内
    {
        for(int i=c;i<=d;i++) // 遍历c到d的范围
            if(solve(x+i,delta,side^1) == side) return dp[x][side]=side; // 如果递归调用solve函数返回的结果等于side，说明找到了解决方案，返回side
    }
    return dp[x][side]=side^1; // 如果没有找到解决方案，返回side的异或值
}

int main()
{
    int T;
    cin>>T; // 输入测试用例的数量
    while(T--) // 对于每个测试用例
    {
        cin>>x>>s>>a>>b>>c>>d; // 输入相关参数
        int k=0;
        int delta = s-x; // 计算目标位置与当前位置的距离
        for(int i=0;i<delta;i++)
            dp[i][0]=dp[i][1]=-1; // 初始化dp数组
        if(solve(0, delta, 1))cout<<1<<endl; // 如果solve函数返回的结果为真，输出1
        else cout<<2<<endl; // 否则输出2
    }
}