[HAOI2008]木棍分割题解

2024-01-05 04:18
文章标签 分割 haoi2008 题解 木棍

本文主要是介绍[HAOI2008]木棍分割题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

分析

第一问是最简单的二分答案,就不说了。第二问则要用到dp中的隔板法,对于本题就是找到一个节点i能到达的最左端lef[i](连续子段和<=第一问中的答案),f[i][j]代表前i个数分成j块的方案数,则f[i][j]=Σ f[k][j-1] (k>=lef[i]&&k<i) ,而因为空间问题,是不可以开1000x50000数组的,所以一个数组f记录当前j的所有i的答案,而s记录j-1的所有i的答案的前缀和。每次求完本轮之后再更新s。
时间:2500ms。
上代码

#include<bits/stdc++.h>
using namespace std;
int now=0,n,m,al[50010],l=1,r=50000000,ans1,mod=10007,ans2,f[50005],s[50005],lef[50005];
bool work(int x){int k=0,t=1;for(int i=1;i<=n;i++)if(al[i]>x)return false;else if(k+al[i]>x){t++,k=al[i];if(t>m) return false;}else k+=al[i];return true;
}
int main(){memset(f,0,sizeof(f));scanf("%d%d",&n,&m);m++;for(int i=1;i<=n;i++)scanf("%d",&al[i]);while(l<=r){int mid=(l+r)/2;if(work(mid))r=mid-1,ans1=mid;elsel=mid+1;}for(int i=1;i<=n;i++){al[i]+=al[i-1];while(al[i]-al[now]>ans1)now++;lef[i]=now;}fill(s,s+n+1,1);for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)f[j]=(s[j-1]-s[lef[j]-1])%mod;s[0]=0;for(int j=1;j<=n;j++)s[j]=f[j]+s[j-1];ans2=(ans2+f[n])%mod;}printf("%d %d\n",ans1,ans2);return 0;
}

这篇关于[HAOI2008]木棍分割题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/571620

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Python如何将大TXT文件分割成4KB小文件

《Python如何将大TXT文件分割成4KB小文件》处理大文本文件是程序员经常遇到的挑战,特别是当我们需要把一个几百MB甚至几个GB的TXT文件分割成小块时,下面我们来聊聊如何用Python自动完成这... 目录为什么需要分割TXT文件基础版:按行分割进阶版:精确控制文件大小完美解决方案:支持UTF-8编码

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

使用Python实现批量分割PDF文件

《使用Python实现批量分割PDF文件》这篇文章主要为大家详细介绍了如何使用Python进行批量分割PDF文件功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、架构设计二、代码实现三、批量分割PDF文件四、总结本文将介绍如何使用python进js行批量分割PDF文件的方法

使用Python将长图片分割为若干张小图片

《使用Python将长图片分割为若干张小图片》这篇文章主要为大家详细介绍了如何使用Python将长图片分割为若干张小图片,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果1. Python需求

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室