[DP] Codeforces #626F. Group Projects

news/2024/2/27 20:53:57

显然是 DP 。这种贡献和最值有关的,一般用按顺序插入的方法 DP ,会简单很多。有挺多类似的题的。
这题就是 fi,j,k 表示插入了前 i 个,有 j 个块开发待插入,总代价为 k
每次插入 i+1 就考虑是新开一个块还是插入原有块中,是否要闭合块。转移 O(1)
有个问题就是一个块的贡献是延迟计算的,即闭合后才会确定贡献。 k 应该记什么呢?
比较直接的想法就是新开块时ai,闭合时 +ai ,但是发现这样会导致 k 取值范围大,状态数就炸了。
所以我们应该假设当前的 ai 是每个块的最大值, i 增大时加上 (ai+1ai)j 就好了。
总体来说比较套路吧。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=205,maxk=1005,MOD=1e9+7;
typedef long long LL;
int n,K,a[maxn];
LL f[2][maxn][maxk],ans; 
int main(){freopen("cf626F.in","r",stdin);freopen("cf626F.out","w",stdout);scanf("%d%d",&n,&K);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);f[0][0][0]=1; a[0]=a[1]; for(int i=0;i<=n-1;i++){memset(f[(i&1)^1],0,sizeof(f[(i&1)^1]));  for(int j=0;j<=i;j++)for(int k=0;k<=K;k++) if(f[i&1][j][k]&&k+j*(a[i+1]-a[i])<=K){(f[(i&1)^1][j+1][k+j*(a[i+1]-a[i])]+=f[i&1][j][k])%=MOD; //新  (f[(i&1)^1][j][k+j*(a[i+1]-a[i])]+=f[i&1][j][k])%=MOD; //新 闭 if(j) (f[(i&1)^1][j][k+j*(a[i+1]-a[i])]+=f[i&1][j][k]*j%MOD)%=MOD; // 插入  if(j) (f[(i&1)^1][j-1][k+j*(a[i+1]-a[i])]+=f[i&1][j][k]*j%MOD)%=MOD; // 插入 闭 }      }for(int i=0;i<=K;i++) ans=(ans+f[n&1][0][i])%MOD;printf("%lld\n",ans);return 0;
}

http://www.ppmy.cn/news/937217.html

相关文章

CodeForces-626C-Block Towers

传送门&#xff1a;http://codeforces.com/problemset/problem/626/C 题意&#xff1a;给你两个1e6的数n&#xff0c;m。n代表有多少个可以用两块砖的学生&#xff0c;m代表有多少个可以用三块砖的学生。每个学生的砖都不能相同&#xff0c;问你最大的高度的最小值。 思路&am…

android和MTKP60哪个好,骁龙626和联发科P60哪个好 联发科P60与骁龙626区别对比

我们知道手机处理器芯片厂商&#xff0c;无非就那么几家。其中除了高通占据第一大市场之外&#xff0c;其他均被华为、三星、联发科和苹果占据。说到联发科芯片&#xff0c;我们不得不提今年新上市的联发科P60处理器&#xff0c;这颗芯片有着极为出色的性能&#xff0c;已经定位…

cf-626c

http://codeforces.com/problemset/problem/626/C 想着暴力过。。。结果可想而知 #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<…

leetcode-SQL-626. 换座位

leetcode-SQL-626. 换座位 题目解题 题目 题目链接 表: Seat ---------------------- | Column Name | Type | ---------------------- | id | int | | name | varchar | ---------------------- Id是该表的主键列。 该表的每一行都表示学生的姓名和I…

NYOJ626 intersection set

原题链接 用C结果TLE了三次&#xff0c;换成C就过了..时间&#xff1a;744&#xff0c;内存&#xff1a;424 #include <cstdio> #include <algorithm> #define MAX 50000 2 int a[MAX]; using namespace std;int main(){int m, n, i, t, sum;while(scanf("%…

CF626C Block Towers 题解

提供一个简单的做法。 upd&#xff1a;将 k k k 改成了 p p p&#xff0c;本人眼瞎 题目传送门 首先&#xff0c;我们设答案为 p p p&#xff0c;则 p p p 至少要等于 max ⁡ ( 2 n , 3 m ) \max(2\times n,3\times m) max(2n,3m) &#xff0c;这个应该很好想&#x…

SS626V100 SDK安装编译osdrv问题汇总

文章目录 前言1、开发环境2、在 linux 服务器上安装交叉工具链2.1 安装 aarch64-mix410-linux.tgz2.2 安装 cc-riscv32-cfg11-musl-20211008-elf.tar.gz2.3 检查工具链版本&#xff0c;打印版本则表示配置成功 3、安装 SDK3.1 SS626V100 SDK 包位置3.2 解压缩并展开 SDK 包 4、…

【LeetCode-SQL】626. 换座位

目录 一、题目二、解决1、if / case when2、row_number()3、left join4、异或 三、参考 一、题目 表: Seat ---------------------- | Column Name | Type | ---------------------- | id | int | | name | varchar | ---------------------- Id是该表…

626 事件

1、 2、 AAB DDA AADB CB

​LeetCode刷题实战626:换座位

算法的重要性&#xff0c;我就不多说了吧&#xff0c;想去大厂&#xff0c;就必须要经过基础知识和业务逻辑面试算法面试。所以&#xff0c;为了提高大家的算法能力&#xff0c;这个公众号后续每天带大家做一道算法题&#xff0c;题目就从LeetCode上面选 &#xff01; 今天和大…

LeetCode 数据库 627、620、626、601、596、595、197、176、175

LeetCode 627 解题思路&#xff1a; if (sex ‘m’,‘f’,‘m’);char(ascii(‘m’) ascii(‘f’) - ascii(sex)); LeetCode 620 解题思路&#xff1a; select * from cinema where id%2 1 and description ! ‘boring’ order by rating desc LeetCode 626 解题思路&am…

改善压降过大的六种方法

改善压降过大的六种方法 当进行完压降仿真完之后,如果结果都是PASS的话是我们最希望看到的,但是时常会因为某些原因,导致压降不通过,下面介绍几种弥补压降的几种措施 方法一 靠近用电端 如下图,电源放的离用电端太远将电源模块尽量靠近用电端放置,尤其是小电压大电流的电…

【 Python 全栈开发 - 人工智能篇 - 42 】逻辑回归算法

一、逻辑回归 1.1 概念 逻辑回归是一种经典的监督学习算法&#xff0c;用于解决二分类问题。它利用一个 S 形函数&#xff08;通常是sigmoid函数&#xff09;将输入特征映射到 0 到 1 之间的概率值&#xff0c;然后根据设定的阈值来判断样本属于哪一类别。逻辑回归常用于预测…

js 生成指定范围的随机数

要在 JavaScript 中生成指定范围的随机数&#xff0c;可以使用 Math.random() 方法生成一个 0&#xff08;包括&#xff09;到 1&#xff08;不包括&#xff09;之间的随机小数&#xff0c;然后通过一些计算将其转换为指定范围内的随机数。 下面是一个示例&#xff0c;演示如何…

Vscode自定义注释模板

首先安装插件Doxygen Documentation Generator&#xff0c;安装完成之后点击Doxygen插件的设置&#xff0c;按照下面的步骤打开settings.json进行编辑&#xff1a; 在settings.json中追加如下代码&#xff1a; "doxdocgen.file.copyrightTag": ["Copyright (C),…

优化类问题建模解析

模型建立阶段 线性规划模型&#xff1a;目标函数和约束条件均为线性 整数规划或0-1规划&#xff1a;决策变量取值被限制为整数或0、1 动态优化模型&#xff1a;以时间为划分阶段的动态过程优化问题 非线性规划模型&#xff1a;目标函数或约束条件中包括非线性函数 多目标规划模…

软件研发开发人员成本计算器

写了个简单的人员工资计算器&#xff0c;用最简单的人天数计算研发投入&#xff0c;其他费用计算稍后补充完善 软件研发成本计算 ——高级工程师中级工程师初级工程师平均日工资项目阶段高级工程师人天中级工程师人天初级工程师人天调研方案产品设计软件开发测试部署培训试运…

PPT转换成PDF文件的方法

PPT转换成PDF文件的方法遇到个头疼的问题&#xff0c;要把PPT转换成PDF格式的文件&#xff0c;不知道该怎么办!在网上搜索了好久看到各种不同的软件&#xff0c;平时没有遇到过也没有使用过&#xff0c;现在好多软件一下都出来了&#xff0c;也不知道到底哪个软件才是比较好的。…

PPT怎么转换成PDF?有哪些转换方法?

一般我们都习惯用PPT来制作演讲稿或课件等&#xff0c;这样便于用幻灯片演示&#xff0c;但一般这样的文档页数都比较多&#xff0c;而且大量图片文件也会比较大&#xff0c;在传送和阅读起来不太方便&#xff0c;所以常将PPT转成PDF使用&#xff0c;教你3个免费转换的方法。 …

如何把PPT转换成pdf格式的文件

只要有wps或Word office会员的都可以转换&#xff0c; 打开ppt文件点击左上角的【文件】点击输出为pdf点击执行即可
最新文章