首页 > 其他分享 >P4544 [USACO10NOV] Buying Feed G

P4544 [USACO10NOV] Buying Feed G

时间:2024-08-02 11:51:45浏览次数:13  
标签:Feed ll P4544 long times USACO10NOV pair dp define

思路:

考虑动态规划算法。

定义 \(dp_{i,j}\) 表示达到第 \(i\) 家商店时共买了 \(j\) 吨饲料的最小花费,那么我们可以枚举到达上一家店的饲料数 \(k\):

\[dp_{i,j} = (x_i-x_{i-1}) \times j^2 + \min\limits_{k=j-f_{i-1}}^j dp_{i-1,k} + c_{i-1} \times (j-k) \]

可以将和 \(i-1\) 与 \(i\) 有关的提到一边,这样可以方便转移:

\[dp_{i,j} = (x_i-x_{i-1}) \times j^2 + c_{i-1} \times j + \min\limits_{k=j-f_{i-1}}^j dp_{i-1,k} - k \times c_{i-1} \]

注意到对于区间 \([j-f_{i-1},j]\),当 \(j\) 增加时,右端点增加 \(1\),左端点也增加 \(1\),那么我们可以使用单调队列维护这个范围的最小值。

时间复杂度为 \(O(MK)\)。

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=505,M=10010,INF=1e18;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	ll x,y,z;
	bool operator<(const Node&rhs)const{
		if(x!=rhs.x)
		  return x<rhs.x;
		return z<rhs.z;
	}
}G[N];
ll n,x,m,l,r,head=0,tail=1;
ll a[N],b[N],c[N],Q[M];
ll dp[N][M];
bool End;
int main(){
//	open("A.in","A.out");
	memset(dp,0x3f,sizeof(dp));
	m=read(),x=read(),n=read();
	for(int x,y,z,i=1;i<=n;i++){
		x=read(),y=read(),z=read();
		G[i]={x,y,z};
	}
	sort(G+1,G+n+1);
	for(int i=1;i<=n;i++){
		a[i]=G[i].x;
		b[i]=G[i].y;
		c[i]=G[i].z;
	}
	a[n+1]=x;
	dp[1][0]=0;
	for(int i=2;i<=n+1;i++){
		head=1,tail=0;
		for(int j=0;j<=m;j++){
            while(dp[i-1][j]-j*c[i-1]<=dp[i-1][Q[tail]]-Q[tail]*c[i-1]&&head<=tail)
              tail--;
			while(Q[head]<j-b[i-1]&&head<=tail)
			  head++;
        	Q[++tail]=j;
			dp[i][j]=dp[i-1][Q[head]]+(a[i]-a[i-1])*j*j+c[i-1]*(j-Q[head]);
		}
	}
	write(dp[n+1][m]);
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

标签:Feed,ll,P4544,long,times,USACO10NOV,pair,dp,define
From: https://www.cnblogs.com/rgw2010/p/18337769

相关文章

  • F. Feed Cats
    原题链接题解每个点要么喂,要么不喂,我们令\(dp[i]\)为前\(i\)个步骤最多能喂养多少猫,易得\(dp[i]\)是单调不减的我们再维护每个点被包含的区间里的最左端\(l\)这样一来\(dp[i]=max(dp[i-1],dp[l-1]+sum)\)可是如何维护每个点被包含区间的最左端呢?我们先记录下每个右......
  • 关注推送---Feed流,推模式实现的个人分析及其思考。
    本篇文章记录我们实际开发过程中,关注推送场景的个人思考,以及解析。文章目录前言一、关注推送是什么?是什么是Feed流?二、解决关注推送问题的技术方案1.理论模型的选取2.数据类型的选取三、理论模型的选取三、数据类型的选取总结前言⁣⁣⁣⁣⁣⁣⁣⁣本篇文章......
  • 【YOLOv8改进】MSFN(Multi-Scale Feed-Forward Network):多尺度前馈网络
    摘要摘要——高光谱图像(HSI)去噪对于高光谱数据的有效分析和解释至关重要。然而,同时建模全局和局部特征以增强HSI去噪的研究却很少。在本文中,我们提出了一种混合卷积和注意力网络(HCANet),该网络结合了卷积神经网络(CNN)和Transformers的优势。为了增强全局和局部特征的建模,我们设计了......
  • 美食社交--feed服务
    前言:本篇博客Feed服务是美食社交项目内第六篇文章,是写在好友服务之后的一篇博客,大家可以先尝试阅读并编写第五篇–美食社交好友服务的文章之后再阅读此文,效果更佳;因为两者是有联系的!1.概念移动互联网时代,Feed流产品非常常见,比如朋友圈,微博,非常典型的Feed流产品,还有图......
  • 23 feed
      feed=supply,thewateroriginatesfromthrash=novefromsidetosideinaviolentwayflingmyarmsandlegsfastandenergeticallyoutput=thepower,energy,etc.producea 这段文字中的几个关键词描述了游泳的动作和相关的一些概念:1.**feed**-这个词在原......
  • Transformer模型-Feed Forward前馈网络和Relu激活函数的简明介绍
     今天介绍transformer模型的FeedForwardnetwork前馈网络和Relu激活函数背景位置感知Position-Wise前馈网络(FFN)由两个全连接层(fullyconnecteddenselayers,就是线性层(LinearLayer),或密集层(DenseLayer))组成,或者也可以称为多层感知机(MLP:multi-layerperceptron)。 参见:Tr......
  • 【Coursera GenAI with LLM】 Week 3 Reinforcement Learning from Human Feedback Cl
    Helpful?Honest?Harmless?MakesureAIresponseinthose3ways.Ifnot,weneedRLHFisreducethetoxicityoftheLLM.Reinforcementlearning:isatypeofmachinelearninginwhichanagentlearnstomakedecisionsrelatedtoaspecificgoalbytakin......
  • Denoising Implicit Feedback for Recommendation论文阅读笔记
    Abstract​ 隐式反馈的普遍性使它们成为构建在线推荐系统的默认选择。虽然大量的隐式反馈缓解了数据的稀疏性问题,但缺点是它们在反映用户的实际满意度方面没有那么干净。例如,在电子商务中,很大一部分点击并不能转化为购买,许多购买最终会得到负面评论。因此,解释隐式反馈中不可避免......
  • CF1932F Feed Cats
    现在能写了。考虑dp做法。在读入数据之后,我们下意识地对每条线段\((l_i,r_i)\)进行排序。随后经过尝试,我们可以排除以猫的编号为阶段进行dp的方案。因此我们选择以位置为阶段进行dp。设\(dp(i,0/1)\)表示位置\(i\)是否投喂能获得的最大价值。有转移方程(注意\(dp(......
  • InstructGPT《InstructGPT: Training language models to follow instructions with h
    背景GPT-3虽然在各大NLP任务以及文本生成的能力上令人惊艳,但是他仍然还是会生成一些带有偏见的,不真实的,有害的造成负面社会影响的信息,而且很多时候,他并不按人类喜欢的表达方式去说话。在这个背景下,OpenAI提出了一个概念“Alignment”,意思是模型输出与人类真实意图对齐,符合人......