题解 | #小L的三角尺#

题意：

小 L 初始数值 x 为 0，需对两个长度均为 n 的数组 A、B 依次执行 n 次操作，每次操作必须从两种规则中选其一：规则一是将 x 更新为 max (0, x−aᵢ)（aᵢ为数组 A 第 i 个元素），规则二是将 x 更新为 x⊕bᵢ（bᵢ为数组 B 第 i 个元素，⊕表示按位异或），要求计算完成所有 n 次操作后 x 能达到的最大值。

核心思路：

这段代码采用动态规划（DP） 解决该问题，核心思路是：利用二维数组dp[i][j]表示执行完前i次操作后，数值x能否达到j，并将x的上限设为 2047（因异或运算特性，超过该值无意义）以限定状态范围；初始时dp[0][0]=1（未操作时x=0为可达状态），随后遍历每一次操作，对前一次的所有可达状态j，分别执行两种规则得到新状态u（max(0, j-a[i])）和v（j^b[i]），并将dp[i][u]和dp[i][v]标记为可达；最后从最大的数值 2047 开始倒序遍历，找到第一个dp[n][j]为可达的j，即为执行完所有操作后x能达到的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=3010,MAXN=2047;
int a[N],b[N];
int dp[N][MAXN+1]; 
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
     
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=MAXN;j>=0;j--)
        {
            if(!dp[i-1][j]) continue;
            int u=max(0,j-a[i]);
            int v=j^b[i]; 
            dp[i][u]=true;
            dp[i][v]=true; 
        } 
    }
     
    for(int j=MAXN;j>=0;j--)  
     if(dp[n][j]) 
     {
        cout<<j;
        break;
     } 
    return 0;
}