当前位置：首页 > article >正文

11.22糖丸比赛题解

article 2024/11/23 15:28:51

为什么这么多dp！！！

Bottles

1.一道背包问题（还涉及贪心）

2.考虑转移方程，在这道题中，关键变量只有两个 a , b 。第一问很好求，根据贪心，先对瓶子的容量进行降序排序，求前若干个瓶子使他们的容量大于等于所有水的体积时的个数即可。

在选择瓶子最少的情况下，方案是不一定的。通过观察得知，第二问就是要在第一问的个数确定时，求出选择瓶子的水最多的方案。选择了若干个瓶子，就意味着其他的瓶子的水要倒入其中，花费就为他们水的体积之和。然后，考虑转移方程。设 fi 表示当水的体积是 i 时所需要的最少的瓶子数。

显然，根据一般的背包问题，有 fi=maxf i−bj +1 。

同时，根据上面的分析，我们要求的是此时水体积最大的，所以附加上一个 ans 数组， ansi 表示 ansi 表示当容积为 i 时水体积的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
struct node{
	int a,b;
}c[N];
int n,ans,suma,sumb,k=0,f[N*N][N];
bool cmp(node x,node y){
	return x.b>y.b;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i].a;
		suma+=c[i].a;
	}
	for(int i=1;i<=n;i++) cin>>c[i].b;
	sort(c+1,c+n+1,cmp);
	while(sumb<suma) sumb+=c[++k].b;
	cout<<k<<" ";
	memset(f,128,sizeof(f));
	f[0][0]=0;
	//cout<<f[1][1]<<endl;
	for(int i=1;i<=n;i++)
		for(int j=sumb;j>=c[i].b;j--)
			for(int kk=1;kk<=k;kk++){
				f[j][kk]=max(f[j][kk],f[j-c[i].b][kk-1]+c[i].a);
			}
	for(int i=suma;i<=sumb;i++) ans=max(ans,f[i][k]);
	cout<<suma-ans;
	return 0;
}

上课

1.贪心题

2.拆方差的式子，方差等于平方的平均减平均的平方。因为总和固定，所以平均的平方固定，所以最小化平方和即可。假设当前对于 x 已求出最小方差的序列，要求 x+1 的最小方差。因为要最小化平方和，所以要把最小的能加的位置加一。原因是平方和公式增加的量是两倍的原数，所以要原数尽可能小。把初始状态全部取 li，然后考虑增量即可。每次把 x 加上一太慢了，考虑对区间按位处理。记录当前位置有多少个区间可以用来加一。

方差式子整理之后就是：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10,mx=1e6,mod=998244353;
struct query{
    ll x,id,ans;
    friend bool operator<(query xy,query zb){
        return xy.x<zb.x;
    }
}qq[N];
ll n,q,invn,l[N],r[N],cnt[N],ans,ansx;
inline ll p(ll x,ll y){
    if(!y) return 1;
    if(y&1) return p(x,y^1)*x%mod;
    return p(x*x%mod,y>>1);
}
int main(){
    scanf("%lld%lld",&n,&q);
    invn=p(n,mod-2);
    for(ll i=1;i<=n;i++){
        scanf("%lld%lld",&l[i],&r[i]);
        ans+=l[i]*l[i];
        ansx+=l[i];
        cnt[l[i]+1]++;
        cnt[r[i]+1]--;
    }
    for(ll i=0;i<=mx;i++) cnt[i]+=cnt[i-1];
    for(ll i=1;i<=q;i++){
        scanf("%lld",&qq[i].x);
        qq[i].id=i;
    }
    sort(qq+1,qq+q+1);
    for(ll i=1,j=0;i<=q;i++){
        while(ansx<qq[i].x){
            if(qq[i].x-ansx<cnt[j]){
                cnt[j]-=(qq[i].x-ansx);
                (ans+=(qq[i].x-ansx)*(j*2-1)%mod)%=mod;
                ansx=qq[i].x;
                break;
            }
            ansx+=cnt[j];
            (ans+=cnt[j]*(j*2-1)%mod)%=mod;
            j++;
        }
        qq[i].ans=ans;
        qq[i].x%=mod;
    }
    sort(qq+1,qq+q+1,[](query xy,query zb){
        return xy.id<zb.id;
    });
    for(ll i=1;i<=q;i++)
        printf("%lld\n",(qq[i].ans*invn%mod-qq[i].x*qq[i].x%mod*invn%mod*invn%mod+mod)%mod);
    return 0;
}

Pictures with Kittens (hard version)

1.单调队列优化dp。

2.用 f[i][j] 表示前 i 个数一共取 j 个且第 i 个一定取所得到的最大答案。

不难写出转移方程：f[i][j]=max{f[p][j−1]}+a[i](i−k≤p<i)

考虑优化：

注意到可以转移的区间长度不变，要求的是区间 [i−k,i−1] 内的最小值，可以采用单调队列。

tips：通过单调队列，第一次更新即为最优答案，如果不进行初始化，但是本题可能会存在一种情况，即非法情况可能转移至合法情况，导致答案非法，说的清楚一点，即转移中可能会存在同一个数被加多次的情况，开始把 f 数组赋为负无穷，否则得到的答案可能比正确答案大。

记得特判。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
int n,k,x,le=1,ri=0;
ll f[N][N];
int q[N],a[N];
int main(){
	scanf("%d%d%d",&n,&k,&x);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memset(f,0xcf,sizeof(f));
	if(n/k>x){
		puts("-1");
		return 0;
	}
	f[0][0]=0;
	for(int j=1;j<=x;j++){
		le=1,ri=0;
		q[++ri]=0;
		for(int i=1;i<=n;i++){
			while(le<=ri&&q[le]+k<i) le++;
			f[i][j]=f[q[le]][j-1]+a[i];
			while(le<=ri&&f[i][j-1]>=f[q[ri]][j-1]) ri--;
			q[++ri]=i;
		}
	}
	ll ans=0;
	for(int i=n-k+1;i<=n;i++) ans=max(ans,f[i][x]);
	printf("%lld\n",ans);
	return 0;
}

Bookshelf G

1.线段树优化dp（怎么这么多dp！）

2.设 fi 表示前 i 本书满足条件时书架高度和的最小值。那么对于当前位置 i，满足宽度限制的最小位置 w 一定不减，可以用指针维护。显然有 fi=min{fj−1+max{Hj,⋯,Hi}}(w≤j≤i)。

把原来的 Hj 变为 Hj∼Hi 的最大值，显然要动态维护 Hw∼Hi 的值，只需支持对 H 后缀取 max⁡ 操作。由于 H 的最大值是不增的，所以取 ⁡max 相当于对一段后缀做区间覆盖。

线段树上二分找到当前要取 max 的分界点，剩下的前缀不会被影响。还需维护区间内 fi 的 ⁡min 和 fi+Hi 的 ⁡min，以及查询 w∼i 中最小的 fi+Hi。

都可以用线段树来维护。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct node{
	int l,r,f,sum,lazy;
}e[N<<2];
int n,w[N],h[N],m,f[N];
int pre[N],st[N],top,L;
void pushup(int u){
	e[u].f=min(e[u<<1].f,e[u<<1|1].f);
	e[u].sum=min(e[u<<1].sum,e[u<<1|1].sum);
	return;
}
void pushdown(int u){
	if(e[u].lazy){
		e[u<<1].lazy=e[u<<1|1].lazy=e[u].lazy;
		e[u<<1].sum=e[u<<1].f+e[u].lazy;
		e[u<<1|1].sum=e[u<<1|1].f+e[u].lazy;
		e[u].lazy=0;
	}
	return;
}
void build(int u,int l,int r){
	e[u].l=l,e[u].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	return;
}
void insert(int u,int x,int val){
	if(e[u].l==e[u].r){
		e[u].f=e[u].sum=val;
		return;
	}
	pushdown(u);
	int mid=e[u].l+e[u].r>>1;
	if(x<=mid) insert(u<<1,x,val);
	else insert(u<<1|1,x,val);
	pushup(u);
	return;
}
void update(int u,int l,int r,int val){
	if(l<=e[u].l && e[u].r<=r){
		e[u].lazy=val;
		e[u].sum=e[u].f+val;
		return;
	} 
	pushdown(u);
	int mid=e[u].l+e[u].r>>1;
	if(l<=mid) update(u<<1,l,r,val);
	if(r>mid) update(u<<1|1,l,r,val);
	pushup(u);
	return;
}
int query(int u,int l,int r){
	if(l<=e[u].l && e[u].r<=r) return e[u].sum;
	pushdown(u);
	int mid=e[u].l+e[u].r>>1;
	int res=1e18;
	if(l<=mid) res=min(res,query(u<<1,l,r));
	if(r>mid) res=min(res,query(u<<1|1,l,r));
	return res;
}
signed main(){
	cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>h[i]>>w[i];
	for(int i=2;i<=n;i++) w[i]+=w[i-1];
	for(int i=1;i<=n;i++){
		while(top&&h[i]>h[st[top]]) top--;
		if(top) pre[i]=st[top];
		else pre[i]=1;
		st[++top]=i;
	}
	build(1,1,n);
	int head=0,nowmaxn=0;
	for(int i=1;i<=n;i++){
		nowmaxn=max(nowmaxn,h[i]);
		while(w[i]-w[head]>L) head++;
		update(1,pre[i],i-1,h[i]);
		if(head==0){
			f[i]=query(1,head+1,i-1);
			f[i]=min(f[i],nowmaxn);
		}
		else f[i]=query(1,head,i-1);
		insert(1,i,f[i]);
	}
	printf("%lld\n",f[n]);
	return 0;
}

总之，dp题挺多的（1道背包，1道单调队列优化，1道线段树优化），不太好写暴力，就当练习dp了。

查看全文

http://www.kler.cn/a/405908.html