H
小L的数组
https://ac.nowcoder.com/acm/contest/120566/H
该题目需要用到动态规划思想,定义一个n+1行2048列的bool类型的二维数组dp,dp[0][0]为true,其余为false,之后从第一行开始,按照两个规则分别进行,得出的两个数,并将相对应的列数修改为true,以此进行下去直至最后一行,而最大数也一定在这最后一行,最后再对最后一行进行查找即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> a(n),b(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
vector<vector<bool>> dp(n+1,vector<bool>(2048,false));
dp[0][0]=true;
for(int i=1;i<=n;i++){
for(int j=0;j<2048;j++) {
if(dp[i-1][j]){
int j1=max(0,j-a[i-1]);
dp[i][j1]=true;
int j2=j^b[i-1];
dp[i][j2]=true;
}
}
}
int maxa=0;
for(int i=0;i<2048;i++){
if (dp[n][i]) {
maxa= max(maxa,i);
}
}
cout<<maxa;
return 0;
}
查看20道真题和解析