题目描述
blablabla
样例
const int N=1e4+10;
class segment{
#define lson (u << 1)
#define rson (u << 1 | 1)
public:
int n;
vector<int> mn;
segment(int _n) : n(_n) {
mn.resize(n*4+10);
build(1,0,n);
}
void pushup(int u){
mn[u]=min(mn[lson],mn[rson]);
}
void build(int u, int l, int r){
if (l == r)
{
mn[u]=2e9;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int x, int val){
if (l==r&&x==l)
{
mn[u]=min(mn[u],val);
return;
}
int mid = (l + r) >> 1;
if (x<=mid) modify(lson, l, mid,x, val);
else modify(rson, mid + 1, r,x, val);
pushup(u);
}
int query(int u,int l,int r,int L,int R)
{
if(l>=L&&r<=R) return mn[u];
int mid=(l+r)>>1;
int res=2e9;
if(L<=mid) res=min(res,query(lson,l,mid,L,R));
if(R>mid) res=min(res,query(rson,mid+1,r,L,R));
return res;
}
};
class Solution {
public:
int minimumValueSum(vector<int>& a, vector<int>& b) {
int n=a.size();
a.insert(a.begin(),0);
int m=b.size();
b.insert(b.begin(),0);
int res=0;
vector<vector<int>> dp(n+10,vector<int>(m+10,2e9));
dp[0][0]=0;
vector<segment> tr;
for(int i=0;i<=m+2;i++){
segment t(n);
tr.push_back(t);
}
vector<vector<pair<int,int>>> g(n+10);
for(int i=1;i<=n;i++){
for(auto [v,id]:g[i-1])
{
int nv=(v&a[i]);
if(g[i].empty()||g[i].back().first!=nv){
g[i].emplace_back(nv,id);
}else continue;
}
if(g[i].empty()||g[i].back().first!=a[i]) g[i].emplace_back(a[i],i);
}
tr[0].modify(1,0,n,0,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=min(i,m);j++)
{
int lst=i;
for(int k=g[i].size()-1;k>=0;k--){
if(g[i][k].first==b[j])
{
int l=g[i][k].second,ll=lst;
dp[i][j]=a[i]+tr[j-1].query(1,0,n,l-1,ll-1);
tr[j].modify(1,0,n,i,dp[i][j]);
break;
}else lst=g[i][k].second-1;
}
}
}
if(dp[n][m]>=2e9) return -1;
return dp[n][m];
}
};
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla