给定ai,bi, ci 表示区间[ai,bi]内至少有ci个点, 要求对于所有给定的ai,bi,ci,  至少多少个点才能满足题目的条件

重做这一题学到的一点是, 可以设变量来表示一些东西,然后才能找出约束的条件,  s[i]表示区间0到i内有多少个点,  那么s[bi] - s[ai-1] >= ci 就是约束的条件

当然了,也有隐藏的条件  1>= s[i] - s[i-1] >=0

可以用最长路来求这一题,最短路当然也是可以的。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
using namespace std;
const int INF = <<;
const int N = + ;
struct Node
{
int to, dist, next;
bool operator<(const Node&rhs)const
{
return dist < rhs.dist;
}
}g[N];
int head[N], e;
int dist[N];
void addEdge(int a, int b, int c)
{
g[e].to = b;
g[e].dist = c;
g[e].next = head[a];
head[a] = e++;
}
int dij(int x, int y)
{
priority_queue<Node> q;
for (int i = x; i <= y; ++i)
dist[i] = -INF;
Node cur, tmp;
dist[x] = cur.dist = ;
cur.to = x;
q.push(cur);
while (!q.empty())
{
cur = q.top(); q.pop();
int u = cur.to;
if (dist[u] > cur.dist)
continue;
for (int i = head[u]; i != -; i = g[i].next)
{
int v = g[i].to;
if (dist[v] < dist[u] + g[i].dist)
{
tmp.dist = dist[v] = dist[u] + g[i].dist;
tmp.to = v;
q.push(tmp);
}
}
}
return dist[y];
}
int main()
{
int n, Min, Max, a, b, c;
Node tmp;
while (scanf("%d", &n) != EOF)
{
e = ;
memset(head, -, sizeof(head));
Min = INF, Max = -INF;
for (int i = ; i <= n; ++i)
{
scanf("%d%d%d", &a, &b, &c);
a++;
b++;
Min = min(a - , Min);
Max = max(b, Max);
addEdge(a - , b, c);
}
for (int i = Min+; i <= Max; ++i)
{
addEdge(i - , i, );
addEdge(i, i - , -); }
printf("%d\n", dij(Min, Max));
}
return ;
}

最新文章

  1. 信鸽推送 .NET (C#) 服务端 SDK rest api 调用库(v1.2)
  2. 【vuejs小项目——vuejs2.0版本】单页面搭建
  3. Android 自定义Dialog类,并在Activity中实现按钮监听。
  4. Lock读写锁技术的妙用
  5. iOS开发之生成二维码
  6. 安装samba服务器
  7. jQuery 利用 $.getJson() 实现跨域
  8. zw版【转发&#183;台湾nvp系列Delphi例程】HALCON OverpaintRegion2
  9. POJ2402 Palindrome Numbers 回文数
  10. 【html】【8】div布局[子div在父div居底]
  11. bootstrap 笔记01
  12. mysql回想一下基础知识
  13. OpenGL 茶壶
  14. spring copy中的一个很气人的问题(初学者渣渣的一些感受)
  15. 记录一次无厘头的粗心失误——java后台报错:Unknown column &#39;xxx&#39; in &#39;field list&#39;
  16. redics在windows平台下的使用
  17. Android开发 - 获取Android设备的唯一标识码(Android 6.0或更高)
  18. bzoj1602
  19. URL传入带有%的参数的解决方法
  20. 实现点击到底部、顶部、指定div功能

热门文章

  1. 记一个手游app数据文件的破解
  2. Jetty:配置JSP支持
  3. php 和thinkphp 对excel操作
  4. c#调用语音功能
  5. 14.4.3.4 Configuring InnoDB Buffer Pool Prefetching (Read-Ahead) 配置InnoDB Buffer pool 预读
  6. 引用类中的enum
  7. (76) Clojure: Why would someone learn Clojure? - Quora
  8. Android短信监听(二)——利用ContentObserver实现短信监听
  9. Flex与Java交互(Flex调用java类展示数据)解析xml展示数据
  10. C++晋升之dynamic_cast