正文

[luogup1868]饥饿的奶牛（dp）

蒟蒻zht的博客  蒟蒻zht的博客  2022-09-14  340

关键词：

先把所有区间按照左端点排序

f[i]表示区间0~i的最优解

#include <cstdio>
#include <iostream>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))

int n, v;
int f[3000001];

struct node
{
	int x, y;
}p[150001];

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;
	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;
	return x * f;
}

inline bool cmp(node a, node b)
{
	return a.x < b.x;
}

int main()
{
	int i, j = 1;
	n = read();
	for(i = 1; i <= n; i++) p[i].x = read(), p[i].y = read(), v = max(v, p[i].y);
	std::sort(p + 1, p + n + 1, cmp);
	for(; !p[j].x; j++) f[p[j].y] = p[j].y + 1;
	for(i = 1; i <= v; i++)
	{
		f[i] = max(f[i], f[i - 1]);
		for(; p[j].x == i; j++) f[p[j].y] = max(f[p[j].y], f[i - 1] + p[j].y - p[j].x + 1);
	}
	printf("%d
", f[v]);
	return 0;
}

p1868饥饿的奶牛

P1868饥饿的奶牛题目描述有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。现用汉语翻译为：有N个区间，每个区间x，y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的... 查看详情

洛谷p1868饥饿的奶牛

题解p1868饥饿的奶牛(代码片段)

题目链接：P1868饥饿的奶牛题面有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。现用汉语翻译为：有N个区间，每个区间x，y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有... 查看详情

动态规划洛谷p1868饥饿的奶牛

luogup2344奶牛抗议(树状数组优化dp)(代码片段)

传送门解题思路树状数组优化dp，f[i]表示前i个奶牛的分组的个数，那么很容易得出$f[i]=sumlimits_1leqjleqif[j-1]*(sum[i]gesum[j-1])$，但是这样的时间复杂度是$O(n^2)?$，所以考虑优化，发现必须满足$sum[i]gesum[j-1]?$才能进... 查看详情

[luogup1472]奶牛家谱cowpedigrees（dp）

传送门一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成，这就决定了DP该怎么写。然而我真的没有想到。 f[i][j]表示深度为i节点数为j的个数sum[i][j]表示深度小于等于i节点树为j的个数 #include<cstdio>#de... 查看详情

bzoj1669:[usaco2006oct]hungrycows饥饿的奶牛dp+树状数组+hash

最长上升子序列。虽然数据可以直接n方但是另写了个nlogn的转移：f[i]=max(f[j]+1)(a[j]<a[i])O(n^2)#include<iostream>#include<cstdio>usingnamespacestd;constintN=5005;intn,a[N],f[N],ans;intread()intr=0,f=1;charp=getcha 查看详情

[luogup1578]奶牛浴场（dp）

传送门 O(s2)算法详见论文王知昆--浅谈用极大化思想解决最大子矩形问题我就复制你能把我怎么样QAQ#include<cstdio>#include<iostream>#include<algorithm>#defineN5010#definemax(x,y)((x)>(y)?(x):(y))#definemin(x,y)((x)& 查看详情

[luogup3052][usaco12mar]摩天大楼里的奶牛cowsinaskyscraper（dp）

传送门输出被阉割了。只输出最少分的组数即可。f数组为结构体f[S].cnt表示集合S最少的分组数f[S].v　表示集合S最少分组数下当前组所用的最少容量f[S]=min(f[S],f[S-i]+a[i])(i∈S)运算重载一下即可。 ——代码1#include&l... 查看详情

[luogup2915][usaco08nov]奶牛混合起来mixedupcows（dp）

传送门 f[i][S]表示当前集合为S，最后一个数为i的最优解f[i][S]+=f[j][S-i](j,i∈S&&j!=i&&abs(a[i]-a[j])>k) ——代码1#include<cstdio>2#include<iostream>3#defineLLlonglong45i 查看详情

[luogup2858][usaco06feb]奶牛零食treatsforthecows（dp）

传送门 f[i][j][k]表示左右两段取到i....j时，取k次的最优解可以优化k其实等于n-j+i则f[i][j]=max(f[i+1][j]+a[i]*(n-j+i),f[i][j-1]+a[j]*(n-j+i))边界f[i][i]=a[i]*n递推顺序不好求，所以选择记忆化搜索。 ——代码1#include<cstdio>2#incl 查看详情

luogup2925干草出售0-1背包问题(代码片段)

LuoguP2925干草出售一、题目二、参考代码2.1二维dp2.2一维dp一、题目农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车... 查看详情

luogup2925干草出售0-1背包问题(代码片段)

清北前紧急补课6饥饿的奶牛(代码片段)

题目描述有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。现用汉语翻译为：有N个区间，每个区间x，y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。对于奶牛... 查看详情

luogup2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情

luogup2345奶牛集会

二次联通门: luoguP2345奶牛集会 /*luoguP2345奶牛集会权值线段树以坐标为下标，坐标为值建立线段树对奶牛按听力由小到大排序对于要查的牛每次第i次放入奶牛起作用的v就是vi；　　每次ans+=（xi*sum-sumxl）*vi+（... 查看详情

luogup1154奶牛分厩[数论]

题目描述农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会... 查看详情