求一个有n个元素的数列,满足任意连续p个数的和不小于s, 任意连续q个数的和不大于t。

令sum[i]表示前i项的和(0<=i<=n,sum[0]=0) 那么题目的条件可转化为: sum[i]-sum[i-p]>=s (p<=i<=n) sum[i]-sum[i-q]<=t (q<=i<=n) 将第一个不等式取反,得到 sum[i-p]-sum[i]<=-s(p<=i<=n)

于是问题转化为求一系列不等式的解,这是一个典型的差分约束问题。 考虑最短路径的性质,令dis[i]表示从s到i的最短路,则对于图中存在的一条边(u,v),有 dis[v]<=dis[u]+w(u,v),即dis[v]-dis[u]<=w(u,v); 类比不等式,于是可建图,i向i-p引长度为-s的边,i-q向i引长度为t的边。 然后运行bellmanford,如果存在负环,则无解, 否则所得到的最短路的值就是sum[i]的一个解。 时间复杂度:O(VE) 具体原理及证明见《算法导论》P387

注意这里只需要求出可行解,故而建立一个虚拟结点的方法是可行的。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,p,q,K1,K2;
queue<int>Q;
bool inq[510];
int dis[510],sumv[510];
int v[510*3],__next[510*3],e,w[510*3],first[510],cnts[510];
void AddEdge(int U,int V,int W){
v[++e]=V;
w[e]=W;
__next[e]=first[U];
first[U]=e;
}
bool spfa(const int &s)
{
memset(dis,0x7f,sizeof(dis));
dis[s]=0; Q.push(s); inq[s]=1; ++cnts[s];
while(!Q.empty())
{
int U=Q.front();
for(int i=first[U];i;i=__next[i])
if(dis[v[i]]>dis[U]+w[i])
{
dis[v[i]]=dis[U]+w[i];
if(!inq[v[i]])
{
Q.push(v[i]);
inq[v[i]]=1;
++cnts[v[i]];
if(cnts[v[i]]>n+1)
return 0;
}
}
Q.pop(); inq[U]=0;
}
return 1;
}
int main(){
scanf("%d%d%d%d%d",&n,&p,&q,&K1,&K2);
for(int i=0;i+p<=n;++i){
AddEdge(p+i,i,-K1);
}
for(int i=0;i+q<=n;++i){
AddEdge(i,q+i,K2);
}
for(int i=0;i<=n;++i){
AddEdge(n+1,i,0);
}
if(!spfa(n+1)){
puts("No");
return 0;
}
puts("Yes");
for(int i=1;i<=n;++i){
sumv[i]=dis[i]-dis[0];
}
for(int i=1;i<n;++i){
printf("%d ",sumv[i]-sumv[i-1]);
}
printf("%d\n",sumv[n]-sumv[n-1]);
return 0;
}

最新文章

  1. HoloLens开发手记 - Unity之Spatial Sounds 空间声音
  2. 设计模式:建造者模式(Builder)
  3. nginx源码分析—内存池结构ngx_pool_t及内存管理
  4. 21.Merge Two Sorted Lists(链表)
  5. Run busybox httpd with php, sqlite
  6. ASP.NET中页面加载时文本框(texbox控件)内有文字获得焦点时文字消失
  7. LC-检索
  8. 查看htmlView
  9. 在ireport中使用checkbox
  10. ASP.NET Core 1.0 部署 HTTPS
  11. form表单1的ajax验证
  12. 大多数时候是软件的Bug,但是... 有时候的确是硬件的问题!
  13. git tag本地删除以及远程删除
  14. 洛谷.2234.[HNOI2002]营业额统计(Splay)
  15. 解决.net+steeltoe服务客户端被服务调用出现400BadRequst错误
  16. linux上,mysql使用聚合函数group by 时报错:SELECT list is not in GROUP BY clause and contains nonaggre的问题
  17. 一个exception
  18. Spring Boot Application 事件和监听器
  19. 20165203《Java程序设计》第五周学习总结
  20. MapReduce 中的两表 join 几种方案简介

热门文章

  1. react-native中使用Echarts,自己使用WebView封装Echarts经验
  2. Linux内核中链表的实现与应用【转】
  3. BZOJ 4241: 历史研究——莫队 二叉堆
  4. Educational Codeforces Round 26 F. Prefix Sums 二分,组合数
  5. 设计模式之笔记--组合模式(Composite)
  6. STL之顺序容器 deque 动态数组
  7. ORACLE导入Excel数据
  8. ubuntu命令行操作mysql常用操作
  9. Author name disambiguation using a graph model with node splitting and merging based on bibliographic information
  10. PHP设计模式二-------单例模式