首页 > 其他分享 >51nod-3928方伯伯的玉米田

51nod-3928方伯伯的玉米田

时间:2024-07-28 11:19:15浏览次数:14  
标签:51nod 3928 玉米田 int Html https ak

https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338

https://class.51nod.com/Html/Textbook/Problem.html#problemId=3928&textbookChapterId=725

image-20240728110946410

保证右端点为 \(n\) 是因为如果不是这样操作,可能导致后面的数大小关系发生变化,而如果保证了,那么后面的数都增加了,不需要考虑大小关系的变化,只需要考虑变化的交界处即可。上面的代码是删去 \([a+1,i-1]\)。

注意写代码的时候更新完答案不能立刻塞入二维树状数组,因为这道题要满足三维偏序:\(a<i,b\le j,a_a+b\le a_i+j\),其实一维已经被我们的枚举顺序搞掉了。

#include<iostream>
using namespace std;
const int N=10010,K=510,AK=5510;
int n,k,a[N],f[N][K],ak;
int c[K][AK];
void add(int x,int y,int v){
	for(;x<=k+1;x+=x&-x)
		for(int i=y;i<=ak;i+=i&-i)
			c[x][i]=max(c[x][i],v);
}
int sum(int x,int y){
	int res=0;
	for(;x;x-=x&-x)
		for(int i=y;i;i-=i&-i)
			res=max(res,c[x][i]);
	return res;
}
int main(){
	#ifdef LOCAL
	freopen("1.txt","r",stdin);
	#endif
	#ifndef LOCAL
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	#endif
	cin>>n>>k;
	for(int i=1;i<=n;++i)
		cin>>a[i],ak=max(ak,a[i]);
	ak+=k;
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=k;++j){
			f[i][j]=sum(j+1,a[i]+j)+1;
			ans=max(ans,f[i][j]);
		}
		for(int j=0;j<=k;++j)add(j+1,a[i]+j,f[i][j]);
	}
	cout<<ans;
	return 0;
}

标签:51nod,3928,玉米田,int,Html,https,ak
From: https://www.cnblogs.com/wscqwq/p/18327988

相关文章

  • 51nod-3986-免费的馅饼
    https://class.51nod.com/Html/Textbook/Problem.html#problemId=3986&textbookChapterId=725https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338我们将馅饼表示为\((p_i,t_i)\),即一个平面直角坐标系上的点。我们把馅饼看成静止,人每次往......
  • 51nod-3976-最长序列
    https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338https://class.51nod.com/Html/Textbook/Problem.html#problemId=3976&textbookChapterId=725LIS是符号只有大于或小于,所以这道题就是LIS问题。状态设计同LIS,由于答案就是长度,所以就能知......
  • 51nod-基因匹配+luogu-【模板】最长公共子序列
    https://www.luogu.com.cn/problem/P1439https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338以上两个都是特例,一个是每个元素不重复,一个是每个元素均有5个。正确性说明参考:https://www.luogu.com.cn/article/1bcs9052由于一般情况可能出......
  • 51nod-3978列车
    https://class.51nod.com/Html/Textbook/Problem.html#problemId=3978&textbookChapterId=724https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337这里一次发车的转移是\([j+1,i]\),出发时间\(+s\)为\(j+1\)启程返回,偏移\(i-j-1\)就......
  • 51nod-1288汽油补给
    1288汽油补给https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337这道题算DP纯粹是个幌子,其实就是一个贪心的过程。为什么要留后面价格贵的油?因为可能不够用,先存着;而如果前面的贵,由于有\(T\)限制,所以在能够装满的同种情况下,用后面......
  • 51nod-3983走方格
    https://class.51nod.com/Html/Textbook/Problem.html#problemId=3983&textbookChapterId=724https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337移动与时间段有关,如果按照时间段划分状态那么每一段内只有一条线性的转移。需要一行一行或......
  • 327. 玉米田
    //327.玉米田.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。//#include<iostream>usingnamespacestd;/*https://www.acwing.com/problem/content/329/农夫约翰的土地由M×N个小方格组成,现在他要在土地里种植玉米。非常遗憾,部分土地是不育的,无......
  • 51nod2599 最近公共祖先LCA
    给定一颗n个节点的树,根节点编号为1,有Q组询问,每次给定一对节点编号(x,y),求(x,y)的最近公共祖先。求LCA有多种方法,这里给的是倍增法,预处理时间O(nlogn),单次查询时间O(logn),支持在线。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definerep(i,a,b)for......
  • 51nod1174 区间中最大的数RMQ
    给出一个有n个数的序列,下标0~n-1,有Q次查询,每次询问区间[l,r]的最大值。如果有修改,可以考虑线段树,这里只有静态查询,可以用ST表,预处理时间O(nlogn),单次查询时间O(1)。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definerep(i,a,b)for(inti=a;i<=b;i......
  • 51nod 2620 序列问题
    原题首先\(O(n\logn)\)的贪心很好想,显然用堆,每次合并两个权值最小的即可然后考虑\(O(n)\)怎么做?我们发现这个权值\(\max(a_i,a_{i+1})\)的\(\max\)很不好处理,因此我们考虑把他优化一下使用单调栈可以求出权值为\(a_i\)的合并区间,然后我们发现对于合并一个区间答案......