线段树
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
const LL inf=3e9;
int n,q;
int a[N];
struct node{
int l,r;
LL tmax,lmax,lmin,rmax,rmin,mul;
}tr[N*4];
void check(LL &x){
if(x>inf) x=inf;
if(x<-inf) x=-inf;
}
node pushup(node&t,node&l,node&r){
t.lmax=max({l.lmax,l.mul*r.lmax,l.mul*r.lmin});
check(t.lmax);
t.rmax=max({r.rmax,r.mul*l.rmax,r.mul*l.rmin});
check(t.rmax);
t.lmin=min({l.lmin,l.mul*r.lmax,l.mul*r.lmin});
check(t.lmin);
t.rmin=min({r.rmin,r.mul*l.rmax,r.mul*l.rmin});
check(t.rmin);
t.mul=l.mul*r.mul;
check(t.mul);
t.tmax=max({l.tmax,r.tmax,l.rmax*r.lmax,l.rmin*r.lmin});
check(t.tmax);
return t;
}
void build(int u,int l,int r){
tr[u]={l,r};
if(l==r){
tr[u].lmax=tr[u].rmax=max(1,a[l]);
tr[u].lmin=tr[u].rmin=min(1,a[l]);
tr[u].tmax=max(1,a[l]);
tr[u].mul=a[l];
return ;
}
else{
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
}
void modify(int u,int x,int v){
if(tr[u].l==x&&tr[u].r==x)
{
tr[u].lmax=tr[u].rmax=max(1,v);
tr[u].lmin=tr[u].rmin=min(1,v);
tr[u].tmax=max(1,v);
tr[u].mul=v;
return ;
}
else{
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
}
node query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u];
}
else{
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else{
node a=query(u<<1,l,r);
node b=query(u<<1|1,l,r);
node res;
pushup(res,a,b);
return res;
}
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--)
{
int opt, x, y;
cin >> opt >> x >> y;
if(opt==1)
{
modify(1, x, y);
}
else {
node res = query(1, x, y);
if (res.tmax > (1 << 30)) cout << "Too large\n";
else cout << res.tmax << '\n';
}
}
return 0;
}
第二题dp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010,M=2*N;
int h[N], e[M], ne[M],idx;
int w[N];
int f[N][N];
int n,m,sz[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int fa){
f[u][0]=0;
sz[u]+=1;
for(int i=h[u];~i;i=ne[i])
{
int son=e[i];
if(son==fa) continue;
dfs(son,u);
//枚举体积 体积=sz[u]+sz[son]-1(除去根节点)
for(int j=sz[u]+sz[son]-1;j>=0;j--)
{
//枚举物品
//真实每组能选的物品其实只取决于当前组
//枚举的有效决策是 f[son][0] f[son][1].....f[son][sz[son]]
// for(int k=0;k<=sz[son];k++)换成这个会tle
for(int k=max(0,j-sz[u]);k<=j;k++)
{
if(k>sz[son]) continue;
f[u][j]=min(f[u][j],f[u][j-k]+f[son][k]);
}
}
sz[u]+=sz[son];
}
//最后来一次总的更新
int cnt=sz[u];
for(int j=cnt-1;j>=0;j--){
f[u][cnt-1]=min(f[u][cnt-1],f[u][j]+w[cnt-j]);
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;
memset(h, -1, sizeof h);
for(int i=2;i<=n;i++) cin>>w[i];
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
add(a, b);
add(b,a);
}
memset(f,0x3f,sizeof(f));
dfs(1,-1);
cout<<f[1][n-1];
}