首页 > 其他分享 >P3195 [HNOI2008] 玩具装箱

P3195 [HNOI2008] 玩具装箱

时间:2024-09-27 13:22:59浏览次数:9  
标签:P3195 que HNOI2008 装箱 dp define

P3195 [HNOI2008] 玩具装箱

\(dp_i\) 表示前 \(i\) 个玩具的最小代价。

\(s_i=\sum_{j\le i} c_i+1\)。

设 \(L'=L+1\)。

\(dp_i=\min_{j<i}\{dp_j+(s_i-s_j-L')^2\}\)

\(dp_i-s_i'^2+2s_iL'=\min_{j<i}\{dp_j+(s_j'+L)^2-2s_is_j\}\)

\(b=y-kx\)

\(k\) 与 \(i\) 有关,对于 \(k_i\),我们要找出一条过点 \((x,y)\) 的斜率为 \(k_i\) 的直线使得直线的截距最小,显然是凸包上的切点,而且是下凸包。因此我们维护下凸包。

因为 \(x\) 单调递增,用单调队列维护下凸包。因为 \(k\) 也是单调递增的,因此我们直接取合法的队首。

Code

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=5e4+6;
int c[N];
int n,L;
ll dp[N];
ll s[N];
struct node{
    ll x,y;
};
node que[N];
int l,r;
ld cal(node a,node b){
    return 1.0*(b.y-a.y)/(b.x-a.x);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    sf("%d%d",&n,&L);
    rep(i,1,n) {
        sf("%d",&c[i]);
        s[i]=c[i]+s[i-1];
    }
    rep(i,1,n) s[i]+=i;
    L++;
    l=r=1;
    que[1]={0,1ll*L*L};
    rep(i,1,n){
        ld k=2*s[i];
        while(l<r&&k>=cal(que[l],que[l+1])){l++;}
        ll b=que[l].y-k*que[l].x;
        dp[i]=b+s[i]*s[i]-2*s[i]*L;
        ll x=s[i],y=dp[i]+(s[i]+L)*(s[i]+L);
        while(r>l&&cal({x,y},que[r])<=cal(que[r],que[r-1])) r--;
        que[++r]={x,y};
        // printf("%lld\n",dp[i]);
    }
    pf("%lld\n",dp[n]);
}

标签:P3195,que,HNOI2008,装箱,dp,define
From: https://www.cnblogs.com/liyixin0514/p/18435498

相关文章

  • [Java基础]拆箱装箱
    在介绍本期文章内容之前,让我们先来看一小段代码:inta=10;Integerb=10;if(b==a){ System.out.println("相等");}执行结果应该大家是毋庸置疑的,10等于10,自然会输出相等。但是有一个问题,a明明是int类型,而b则是Integer类型。两个明显是不同类型的对象,为什么能够相等呢?这......
  • 晃电治理新思路之来自国高电气的新一代预装箱式无扰动快切开闭所
    钢铁产业是国民经济的重要支柱,持续的安全生产是企业得以生存与发展的关键。然而,晃电现象却如同隐形杀手,总是在意想不到的时刻对企业的正常生产造成严重打击。在炼铁工艺中,焦化炼焦是至关重要的一环,对电力的连续性要求极为严格。为了更好地了解客户的需求,国高电气在过去一两年内对河......
  • 【生日视频制作】集装箱红色货车大卡车身AE模板AE模板修改文字软件生成器教程特效素材
    生日视频制作教程集装箱红色货车大卡车身AE模板修改文字特效广告生成神器素材祝福玩法AE模板工程怎么如何做的【生日视频制作】集装箱红色货车大卡车身AE模板AE模板修改文字软件生成器教程特效素材【AE模板】生日视频制作步骤:下载AE模板安装AE软件把AE模板导入AE......
  • 【题解】【动态规划】—— [NOIP2001 普及组] 装箱问题
    【题解】【动态规划】——[NOIP2001普及组]装箱问题[NOIP2001普及组]装箱问题题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.题意解析2.AC代码2.1.二维d......
  • 装箱拆箱(boxing and unboxing)
    1.引用类型和值类型为了理解装箱和拆箱,首先需要了解值类型和引用类型的特点。引用类型:必须从托管堆分配每个对象有一些额外成员,这些成员必须初始化对象中其它字节总是为0从托管堆分配对象,可能强制执行一次垃圾回收从引用类型的特点我们可以知道,如果所有类型都是引用......
  • P3193 [HNOI2008] GT考试 解题报告
    题目传送门题目大意:给定一个长度为\(m\)且只含\(0\sim9\)的字符串\(s\),求出所有长度为\(n\)的,只含\(0\sim9\)且不含\(s\)字符串的数量,结果对\(mod\)取模。数据范围:\(n\le10^9,m\le20,k\le1000\)。思路:不难发现和这道题很像,只是\(n\)的数据范围被扩大到......
  • 值类型和引用类型、装箱和拆箱、静态类和普通类、方法的重载、继承和多态、访问修饰符
    目录一、值类型和引用类型的区别?值类型(ValueTypes)定义:特点:示例:引用类型(ReferenceTypes)定义:特点:示例:举例说明:总结:二、装箱和拆箱装箱(Boxing)特点:示例:拆箱(Unboxing)特点:示例:示例代码:装箱和拆箱的影响最佳实践:三、静态类和普通类的区别?静态类(Static......
  • c#优化装箱拆箱
    1、通过泛型//obj是一个int类型的值类型,在newTest的时候传进去的obj是就会装箱成引用类型,以为Test类是引用类型intobj=2;Testtest=newTest(obj);//通过泛型这里obj传进去的就是值类型,就不需要装箱了Test<int>test=newTest<int>(obj);第一段代码中会发生装箱,因......
  • 值类型和引用类型、装箱和拆箱、静态类和普通类、方法的重载、继承和多态
    目录值类型和引用类型的区别?值类型(ValueTypes)定义:特点:示例:引用类型(ReferenceTypes)定义:特点:示例:举例说明:总结:装箱和拆箱装箱(Boxing)特点:示例:拆箱(Unboxing)特点:示例:示例代码:装箱和拆箱的影响最佳实践:静态类和普通类的区别?静态类(StaticClass)普通......
  • SimPy仿真:集装箱码头如何保证单个集装箱卸货和顺序运输?
    我正在对集装箱码头进行SimPy模拟,船舶到达、停泊并使用起重机卸载集装箱,然后使用卡车进行运输。问题陈述_pt1、问题陈述_pt2我需要确保:每台起重机一次仅卸载一个集装箱。在有空卡车可用之前,起重机应继续其卸载过程,无论之前的卡车是否已完成......