寒假集训6 题解
H-小L的数组
动态规划 位运算 贪心
状态定义：dp[i][j]=1 表示第i次操作后x的值可以为j
状态转移：从dp[i][j]转移到dp[i][max(0,j-a[i])]或dp[i][j^b[i]]
(从i=1到i=n枚举所有的可能性)
值域：由于"a[i],b[i]<4048",且异或操作不会增加位数，所以x最大不超过4047
最后从大到小遍历，即可得到最大值
#include <bits/stdc++.h>
using namespace std;
int a[2050];
int b[2050];
int dp[2050][2050]={0};
void solve(){
int n,x=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
dp[1][max(0,x-a[1])]=1;
dp[1][x^b[1]]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<2048;j++){
if(dp[i-1][j]){
dp[i][max(0,j-a[i])]=1;
dp[i][j^b[i]]=1;
}
}
}
for(int j=2047;j>=0;j--){
if(dp[n][j]){
cout<<j;
return ;
}
}
}
int main()
{
solve();
return 0;
}
