首页 > 其他分享 >关于天数限制的动态规划的一类常见技巧

关于天数限制的动态规划的一类常见技巧

时间:2023-07-23 18:00:43浏览次数:34  
标签:le 技巧 int 天数 ll mid 动态 转移 cur

关于天数限制的动态规划的一类常见技巧

例题:P6647 [CCC2019] Tourism

题目大意:

给定 \(n\) 个景点,每天可以游览至多 \(k\) 个景点,满足用 \(t\) 天浏览,\(t\) 必须最小,能得到的最大评分是多少?

解决方法:

首先不考虑天数限制,考虑动态规划

明显的,设 \(f_i\) 为前 \(i\) 天所能获得的最大评分,一天可以从 \([i-k,i)\) 转移,容易写出状态转移方程:

\[f_i=\max_{i-k\le j<i}\{f_j+\max_{j<k\le i}\{A_k\}\} \]

但是加上天数限制怎么做?

天数最少是不是说明转移次数越少?

那现在每次转移的代价都是一样的,如果我们给每次转移加上一个代价,是不是就可以让 \(f\) 迫不得已选择转移次数少的那个?

那怎么给每个转移加上一个代价呢?

我们是不是只要在转移后面加上一个 \(-\infty\),转移次数越多积累的 \(-\infty\) 越多,是不是就越小?

于是,我们更改状态转移方程,为了更加直观,我们定义 \(Sum(i,j)=\max_{i\le k \le j}\{A_k\}\),则状态转移方程如下:

\[f_i=\max_{i-k\le j<i}\{f_j+Sum(j+1,i)\}-\infty \]

直接暴力的话时间复杂度为 \(O(n^3)\),肯定不行

我们考虑优化转移过程

当我看到 \(i-k\le j<i\) 了,迅速想到了单调队列,但真的可以吗?

我们可以看到 \(Sum(j+1,i)\) 是个定值吗?很明显并不是,所以里面的式子他是在一直变化的,这让我们想到了具有 动态修改功能的线段树可以 \(\log\) 级维护

那变化的值呢?

很明显,如果一个 \(i\) 进来,那么所有比他小的数 \(j\) 都要增加 \(A_i-A_j\) 这个值,什么东西能维护这个东西呢?

能想到用单调栈,如果一个数 \(j\) 被 \(i\) 弹出,那么什么区间会被影响到呢?

自行模拟一下,可以发现 \([T_{top-1},T_{top}-1]\) 这个区间被影响了,区间操作即可

最后把 \(f_{i-1}+A_i\) 这个值进行单修,最后区查即可

Qestion

那如果被 \(j\) 弹掉的 \(k\) 呢?它的大小似乎没有更新

Answer

由于在 \(k\) 的值是小于等于在 \(j\) 的值的,当且仅当在 \(k\) 更新 \(j\) 时取等,这等同于加 \(j\),并没有影响(毕竟是最大值嘛

最后献上代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;

typedef long long ll;

const ll Inf = 1e12;

struct Segt_Tree{//需要实现区查区改单改 
	struct Node {ll sum, lz; }t[4 * MAXN];
	#define ls(i) (i << 1)
	#define rs(i) (i << 1 | 1)
	
	void push_up(int cur) {t[cur].sum = max(t[ls(cur)].sum, t[rs(cur)].sum); }
	void f(int cur, int l, int r, ll k) {
		t[cur].sum += k;
		t[cur].lz += k;
	}
	void push_down(int cur, int l, int r) {
		int mid = l + r >> 1;
		f(ls(cur), l, mid, t[cur].lz); f(rs(cur), mid + 1, r, t[cur].lz);
		t[cur].lz = 0;
	}
	
	void modify_qj(int cur, int l, int r, int x, int y, ll k) {
		if (x <= l && y >= r) {
			f(cur, l, r, k); return ;
		}
		int mid = l + r >> 1; push_down(cur, l, r);
		if (x <= mid) modify_qj(ls(cur), l, mid, x, y, k);
		if (y > mid ) modify_qj(rs(cur), mid + 1, r, x, y, k);
		push_up(cur);	
	}
	void modify_dd(int cur, int l, int r, int x, ll k) {
		if (l == r) {
			f(cur, l, r, k); return ;
		}	
		int mid = l + r >> 1; push_down(cur, l, r);
		if (x <= mid) modify_dd(ls(cur), l, mid, x, k);
		else modify_dd(rs(cur), mid + 1, r, x, k);
		push_up(cur);
	}
	ll query(int cur, int l, int r, int x, int y) {
		if (x <= l && y >= r) return t[cur].sum;
		int mid = l + r >> 1; ll ans = -1e18; push_down(cur, l, r);
		if (x <= mid) ans = max(ans, query(ls(cur), l, mid, x, y));
		if (y > mid ) ans = max(ans, query(rs(cur), mid + 1, r, x, y));
		return ans; 
	}
}t;

int n, k, A[MAXN];

int T[MAXN], tp;

ll F[MAXN];

// f[i]= max{f[j] + g(j+1, i)} - inf

int main () {
	cin >> n >> k;	
	for (int i = 1; i <= n; i ++) cin >> A[i];
	for (int i = 1; i <= n; i ++) {
		while (tp && A[T[tp]] <= A[i]) {
			t.modify_qj(1, 0, n, T[tp - 1], T[tp] - 1, A[i] - A[T[tp]]);
			tp --;
		}
		T[++ tp] = i;
		t.modify_dd(1, 0, n, i - 1, F[i - 1] + A[i]);
		F[i] = t.query(1, 0, n, max(i - k, 0), i - 1) - Inf;
		
	}
	cout << F[n] + ((n - 1) / k + 1) * Inf << '\n';
	return 0;
}

积累到一个 trick好叭(很开心

完结撒花✿✿ヽ(°▽°)ノ✿

标签:le,技巧,int,天数,ll,mid,动态,转移,cur
From: https://www.cnblogs.com/Phrvth/p/17575336.html

相关文章

  • JavaScript程序设计模式小技巧——策略模式,快看快用!!!
    ##前言>系列首发于公众号[『非同质前端札记』](https://mp.weixin.qq.com/s?__biz=MzkyOTI2MzE0MQ==&mid=2247485576&idx=1&sn=5ddfe93f427f05f5d126dead859d0dc8&chksm=c20d73c2f57afad4bbea380dfa1bcc15367a4cc06bf5dd0603100e8bd7bb317009fa65442cdb&token=1071012......
  • 构造、交互题技巧学习小记
    (本文仅包含技巧和例题,无题目解析)抽屉原理抽屉原理通常的表述时,将\(n\)个物品放入\(k\)个抽屉,则其中必有一个抽屉包含至少\(\lceil\fracnk\rceil\)个物品也一定有一个抽屉包含至多\(\lfloor\fracnk\rfloor\)个物品。在一些构造题中,经常会要求构造一个权值至多(少)为某个......
  • java调试技巧
    1.debug断点调试中,查看request中的parameter值一般需要打开request的7-9层才可以找到,(下图已经标上序号)打开第7层找到pathParameter,打开第9层找到parameter的值request->request->request->inputStream->ib->coyoteRequest->parameters->paramHashValues  参考:debug断点调......
  • 递归和动态规划的区别
    有时候根据不同的要求,算法的目的可能是计算特定值,也可能是返回某个要求的全部可能的值。递归就是完全不去控制执行过程的一种算法,如果返回全部可能的值,就极大可能重复执行之前的已有操作。动态规划则是利用一种数据结构,通常可能是列表,保存中间运行的值,减少已经执行的运算,或者根......
  • 如何动态修改 spring aop 切面信息?让自动日志输出框架更好用
    业务背景很久以前开源了一款auto-log自动日志打印框架。其中对于spring项目,默认实现了基于aop切面的日志输出。但是发现一个问题,如果切面定义为全切范围过大,于是v0.2版本就是基于注解@AutoLog实现的。只有指定注解的类或者方法才会生效,但是这样使用起来很不方便。......
  • 使用golang灵活处理动态文案
    代码packagescripts_stroageimport("fmt""github.com/duke-git/lancet/v2/slice""github.com/gogf/gf/util/gconv""github.com/gookit/goutil/dump""regexp""strings"&q......
  • java中tomcat 加载动态库XXX.dll报错“java.lang.UnsatisfiedLinkError: already load
    错误:在Tomcat项目和supermapiserverwar包中使用了相同的supermapjavaiobject【四个jar包】,实际的访问过程如下:这时候在访问Tomcat的时候,就会出现一个错误:anexceptioncaughtatEnvironment.loadLibrary(),programwillcontinuerunning.java.lang.UnsatisfiedL......
  • python函数入参配置的技巧
    如下的代码大家应该都见过:deffunc1(n):ifn<=0:print('请输入一个整数!')func1(int(input()))elifn<=2:return1else:returnfunc1(n-1)+func1(n-2)这个是是一个简单的函数处理,得到斐波那契数列的第N个数的值,这里的入参就......
  • Excel 中的技巧函数
    Excel常用函数公式20例,第7条条件查询,其中第一列为要查询的列,如果不是怎么办?可以参考Excel函数之王,Vlookup到底怎么用?IF({1,0},B:B,A:A)......
  • C#动态库调用webservice
    1.c#调用一外部webservice时,对方能收到数据包,缺收不到正确数据,报莫名错误。对方也不知道原因。只能采用动态调用方式。采用如下类:1publicclassWebserviceHelper2{3///<summary>4///动态调用web服务5///</summary>6......