[USACO09MAR]Cleaning Up
2024-09-07 20:00:55
题目大意:
给你一个长度为n的序列a,你可以将其分为若干段,最终的答案为每一段不同数个数的平方和。
思路:
不难想到一个O(n^2)的DP:
f[i]=min{f[j]+cnt(j,i)^2}
考虑一些优化。
首先不难发现,答案最坏不会超过n。(一个数一段)
要让答案更优,一段内不同数的个数不会超过sqrt(n)。(不然平方之后就超过n了)。
我们把到i有j个不同数的最后位置记作pos[j]。
考虑如何维护这个pos[j]。
我们可以先将每个数字出现的上一个位置记作last[i],一段中出现的不同数字个数记作cnt[i]。
首先,如果last[a[i]]<=pos[j],则cnt[j]++。
当cnt[j]>j时,把左端点往右缩,如果这时last[a[pos[j]]]==pos[j],cnt[j]--。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff;
const int N=,M=;
int a[N],f[N],pos[M],last[M],cnt[M];
int main() {
int n=getint(),m=getint();
for(register int i=;i<=n;i++) {
const int x=getint();
if(x!=a[a[]]) a[++a[]]=x;
}
n=a[],m=sqrt(a[]);
for(register int i=;i<=n;i++) {
f[i]=inf;
for(register int j=;j<=m;j++) {
if(last[a[i]]<=pos[j]) cnt[j]++;
}
last[a[i]]=i;
for(register int j=;j<=m;j++) {
while(cnt[j]>j) {
pos[j]++;
if(last[a[pos[j]]]==pos[j]) cnt[j]--;
}
}
for(register int j=;j<=m;j++) {
f[i]=std::min(f[i],f[pos[j]]+j*j);
}
}
printf("%d\n",f[n]);
return ;
}
最新文章
- Sublime的使用
- 高性能 Oracle JDBC 编程
- windows系统下ftp上传下载和一些常用命令
- Change the Windows 7 Taskbar Thumbnail and List Mode
- oracle_dblink配置
- 过滤3个字节以上的utf-8字符
- dell N5010
- JavaScript的基本类型总结
- JOptionPane的使用
- 玩转 SSH(七):使用 dubbo + zookeeper 实现服务模块化
- 洛谷 P3370 【模板】字符串哈希
- HI3531的nand flash测试
- SpringCloud微服务如何优雅停机及源码分析
- pandas中的空值处理
- Omi框架学习之旅 - 生命周期 及原理说明
- mysql案例-sysbench安装测试
- python3 + selenium 运行过程中进行截图
- SpringBoot 使用Sharding-JDBC进行分库分表及其分布式ID的生成
- deno学习三 官方提供的方便deno 安装方式
- Remote Debugging (2)
热门文章
- 解决LaTex中插入Visio画图有多余边框的问题
- qemu中是怎么模拟的新的设备
- Codeforces Round #388 (Div. 2) 749E(巧妙的概率dp思想)
- 【CZY选讲&#183;棋盘迷宫】
- 【CZY选讲&#183;吃东西】
- php中json_encode和json_decode的用法
- 如何使用 JSP JSTL 显示/制作树(tree) 菜单
- Eclipse EE导入maven工程
- RHN Classic and Red Hat Subscription Management
- 结构型设计模式之桥接模式(Bridge)