https://darkbzoj.cf/problem/1283

给出一个长度为N的正整数序列Ci,求一个子序列,使得原序列中任意长度为M的子串中被选出的元素不超过K(K,M<=100) 个,并且选出的元素之和最大。

http://www.cnblogs.com/137shoebills/p/8871648.html

↑和这道题一样

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,m,k,S,T,SS;
struct nod{
int x,y,v,co,rev,next;
}e[*maxn];
int head[maxn]={},tot=;
int a[maxn]={};
void init(int x,int y,int v,int co){
e[++tot].x=x;e[tot].y=y;e[tot].v=v;e[tot].co=co;e[tot].rev=tot+;e[tot].next=head[x];head[x]=tot;
e[++tot].x=y;e[tot].y=x;e[tot].v=;e[tot].co=-co;e[tot].rev=tot-;e[tot].next=head[y];head[y]=tot;
}
queue<int>q;
int vis[maxn]={},fa[maxn]={},dis[maxn]={};
bool SPFA(){
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
memset(fa,,sizeof(fa));
q.push(S);vis[S]=;dis[S]=;
while(!q.empty()){
int x=q.front();q.pop();vis[x]=;
for(int i=head[x];i;i=e[i].next){
if(!e[i].v)continue;
if(dis[e[i].y]>dis[x]+e[i].co){
dis[e[i].y]=dis[x]+e[i].co;
fa[e[i].y]=i;
if(!vis[e[i].y]){
q.push(e[i].y);vis[e[i].y]=;
}
}
}
}
return fa[T];
}
int doit(){
int val=maxn,ans=;
for(int i=fa[T];i;i=fa[e[i].x])val=min(val,e[i].v);
for(int i=fa[T];i;i=fa[e[i].x]){
e[i].v-=val;e[e[i].rev].v+=val;ans+=e[i].co;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
T=n+;S=T+;SS=S+;
for(int i=;i<=n;i++){
init(i,i+m>n?T:i+m,,-a[i]);
init(i,i+>n?T:i+,k,);
}
for(int i=;i<=m;i++)init(SS,i,maxn,);
init(S,SS,k,);
int ans=;
while(SPFA())ans-=doit();
printf("%d\n",ans);
return ;
}

最新文章

  1. getPx function
  2. PaySignKey
  3. rsyslog日志服务的配置文件分析
  4. PCB阻抗调节
  5. Gridview点击Edit编辑未update和cancel后的问题
  6. JSON基础学习
  7. 基于visual Studio2013解决C语言竞赛题之0205位数求和
  8. nginx添加编译lua模块
  9. 青年菜君与小农女送菜商业模式PK
  10. Spring MVC的文件上传和下载
  11. C语言用regcomp、regexec、regfree和regerror函数实现正则表达式校验
  12. __dirname与__filename
  13. 【Unity笔记】打包安卓APK时Build Setting中的三种Build System
  14. js获取url传值的方法
  15. 关于EOF:
  16. Shell 基础 -- 流编辑器 sed 详解
  17. phaser3 微信小游戏入门
  18. leetcode179
  19. Java之IO(十)Reader和Writer
  20. json 对象里面含有 =的解决办法

热门文章

  1. Linux硬盘镜像获取与还原(dd、AccessData FTK Imager)
  2. aarch64_l4
  3. Python模块:Random(未完待续)
  4. java基础31 List集合下的Vector集合
  5. PHP SPL使用方法 自动加载和迭代器
  6. redis主从,哨兵(windows版)
  7. ****jQuery - 设置HTML内容和属性
  8. Spring介绍及配置(XML文件配置和注解配置)
  9. day8--by a gentlement man
  10. Rookey.Frame企业级快速开发框架开源了