首页 > 其他分享 >NOIP 复习题之动态规划

NOIP 复习题之动态规划

时间:2024-09-14 15:46:59浏览次数:13  
标签:NOIP int ed tree 复习题 res 动态 dp mod

AT_joi2022ho_c 選挙で勝とう

首先要先把协作者买出来,再对于之后的州把买的协作者全部用上。则我们可以先枚举需要的协作者数量 \(x\),可以知道的是:我们枚举选择哪些 \(x\) 个协作者,再在剩下的州中选择 \(A_i\) 最小的 \(K-x\) 个州即可。则考虑 dp。我们对 \(B_i\) 进行排序后,协作者就只在前 \(K\) 个进行买卖。

我们可以发现:当两个协作州之间有反对州时,将反对州与后面一个协作州位置交换一定会更优。则定义 \(f_{i,j}\) 表示前 \(i\) 个州,选 \(j\) 个协作州的最小代价,且前 \(i\) 个州要么协作要么投票。

dp 复杂度 \(O(n^2)\),总复杂度 \(O(n^3)\)。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 505;
int n, k, sum[N][N], cnt;
double dp[N][N], res = 2e9;

struct edge {
	int a, b;
}ed[N];

signed main() {
	cin >> n >> k;
	_for(i, 1, n) cin >> ed[i].a >> ed[i].b;
	_for(i, 1, n) {
		cnt += (ed[i].b != -1);
		if (ed[i].b == -1) ed[i].b = 2e9;
	}
	sort(ed + 1, ed + n + 1, [](edge x, edge y) {
		return x.b < y.b;
	});
	memset(sum, 0x3f, sizeof sum);
	_for(i, 1, n + 1) sum[i][0] = 0;
	_pfor(i, n, 1) {
		_for(j, 1, n - i + 1) {
			sum[i][j] = min(sum[i + 1][j], sum[i + 1][j - 1] + ed[i].a);
		}
	}
	cnt = min(cnt, k);
	_for(cas, 0, cnt) {
		memset(dp, 0x7f, sizeof dp);
		dp[0][0] = 0;
		_for(i, 1, k) {
			_for(j, 0, cas) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1.0 * ed[i].a / (cas + 1));
				if (j) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1.0 * ed[i].b / j);
			}
		}
		_for(i, cas, k) res = min(res, dp[i][cas] + 1.0 * sum[i + 1][k - i] / (cas + 1));
	}
	printf("%.15lf", res);
}

AT_joisc2015_c たのしいたのしい家庭菜園

考虑最后剩下的最高的树,往左边走单调递减,往右边走单调递减。也就是最后剩下了一个上升子序列和下降子序列。

考虑 dp。定义 \(f_i\) 表示前 \(i\) 颗树,第 \(i\) 颗树保留的最大收益。

则 \(f_i=f_j+p_i-\sum_{k=j+1}^{i-1} [h_k>h_j] \times c_k\),且 \(h_j<h_i\)。

仿照 LIS 的线段树优化思路,难以操作的是后面的一堆 sum。可以看出,每个 \(h_k\) 都对之后的 \(h_j<h_k\) 有 \(-c_k\) 的贡献,进而对于 \([1,h_k-1]\) 减去 \(c_k\)。

#include <bits/stdc++.h>
using namespace std;

#define ls p << 1
#define rs p << 1 | 1
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
const int N = 3e5 + 5, INF = -2e18;

int n, b[N], tot, ans = -2e18, f[N], g[N];

struct edge {
	int H, P, C;
}ed[N]; 

struct ss {
	struct stu {
		int l, r, maxn, lazy;
	}tree[N * 4];
	
	void push_up(int p) {
		tree[p].maxn = max(tree[ls].maxn, tree[rs].maxn);
	}
	
	void push_down(int p) {
		if (tree[p].lazy) {
			tree[ls].maxn += tree[p].lazy;
			tree[rs].maxn += tree[p].lazy;
			tree[ls].lazy += tree[p].lazy;
			tree[rs].lazy += tree[p].lazy;
			tree[p].lazy = 0;
		}
	}	
	
	void build(int p, int l, int r) {
		tree[p].lazy = 0; tree[p].maxn = INF; tree[p].l = l, tree[p].r = r;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
	}
	
	void modify(int p, int l, int r, int val) {
		if (l <= tree[p].l && tree[p].r <= r) {
			tree[p].maxn += val;
			tree[p].lazy += val;
			return;
		}
		push_down(p);
		int mid = (tree[p].l + tree[p].r) >> 1;
		if (l <= mid) modify(ls, l, r, val);
		if (r > mid) modify(rs, l, r, val);
		push_up(p);
	}
	
	void modify_max(int p, int x, int val) {
		if (tree[p].l == tree[p].r) {
			tree[p].maxn = max(tree[p].maxn, val);
			return;
		}
		push_down(p);
		int mid = (tree[p].l + tree[p].r) >> 1;
		if (x <= mid) modify_max(ls, x, val);
		else modify_max(rs, x, val);
		push_up(p);
	}
	
	int query(int p, int l, int r) {
		if (l <= tree[p].l && tree[p].r <= r) return tree[p].maxn;
		int mid = (tree[p].l + tree[p].r) >> 1, res = INF;
		push_down(p);
		if (l <= mid) res = max(res, query(ls, l, r));
		if (r > mid) res = max(res, query(rs, l, r));
		return res;
	}
}tr;

signed main() {
	cin >> n;
	_for(i, 1, n) cin >> ed[i].H >> ed[i].P >> ed[i].C, b[++tot] = ed[i].H;
	sort(b + 1, b + tot + 1);
	tot = unique(b + 1, b + tot + 1) - b - 1;
	_for(i, 1, n) ed[i].H = lower_bound(b + 1, b + tot + 1, ed[i].H) - b;
	tr.build(1, 0, tot);
	tr.modify_max(1, 0, 0);
	_for(i, 1, n) {
		f[i] = tr.query(1, 0, ed[i].H) + ed[i].P;
		tr.modify_max(1, ed[i].H, f[i]);
		tr.modify(1, 0, ed[i].H - 1, -ed[i].C);
	}
	tr.build(1, 0, tot);
	tr.modify_max(1, 0, 0);
	_pfor(i, n, 1) {
		g[i] = tr.query(1, 0, ed[i].H) + ed[i].P;
		tr.modify_max(1, ed[i].H, g[i]);
		tr.modify(1, 0, ed[i].H - 1, -ed[i].C);
	}
	_for(i, 1, n) ans = max(ans, f[i] + g[i] - ed[i].P);
	cout << ans << endl;
}

CF1515E Phoenix and Computers

考虑最后的电脑操作形态:\(1\sim X_1\) 手动开启,\(X_1+1\) 自动开启,\(X_1+1\sim X_2\) 手动开启,\(X_2+1\) 自动开启,\(X_{n-1}+1\sim X_n\) 手动开启。

先考虑一个子问题:有 \(n\) 台电脑,都需要手动开启,那么方案数是多少?第一次开第 \(x\) 台电脑,那么 \(x+1,x+2,\dots, n\) 只能相对顺序开启,\(x-1,x-2,\dots,1\) 只能相对顺序开启。那么其余 \(n-1\) 台电脑按相对顺序混杂在一起,等价于其余 \(n-1\) 台电脑,选 \(x-1\) 台电脑的方案数。则总方案数 \(C_{n-1}^{0}+C_{n-1,1}+\dots+C_{n-1}^{n-1}=2^{n-1}\)。

则定义 \(f_{i,j}\) 表示前 \(i\) 台电脑,有 \(j\) 台手动开启的方案数。

转移有:\(f_{i+k+1,j+k}=f_{i,j}\times 2^{k-1}\times C_{j+k}^{k}\)。其中 \(2^{k-1}\) 子问题中解释过,\(C_{j+k}^{k}\) 就是新的和旧的混在一起。

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long

const int N = 405;
int n, mod, b2[N], C[N][N], f[N][N], res;

void init() {
	b2[0] = C[0][0] = 1;
	_for(i, 1, N - 5) b2[i] = b2[i - 1] * 2 % mod;
	_for(i, 1, N - 5) {
		_for(j, 0, N - 5) {
			C[i][j] = C[i - 1][j];
			if (j) C[i][j] = (C[i][j] + C[i - 1][j - 1]) % mod;
		}
	}
}

signed main() {
	cin >> n >> mod;
	init(); 
	_for(i, 1, n) {
		f[i][i] = b2[i - 1];
		_for(j, 0, i) {
			_for(k, 1, n - i - 1) {
				f[i + k + 1][j + k] = (f[i + k + 1][j + k] + f[i][j] * b2[k - 1] % mod * C[j + k][j] % mod) % mod;
			}
		}
	}
	_for(i, 0, n) res += f[n][i], res %= mod;
	cout << res << endl;
}

P10375 [AHOI2024 初中组] 计数

考虑一个可删除区间包含另一个小的可删除区间,那么只保留最大的。而且一个区间如果可删除,一定满足 a....ab....b....z.....z 的形式。

考虑一个数加入但是无效的情况:a.....ab,此时如果加入 \(c\),想要可删除,则必须加入 \(a\) 或 \(b\),则意味着 \(c\) 被覆盖了。此时情况可以概括为:原序列不能被删除,然后加入了一个不能使原序列被删除的字符。

则可以定义 dp 为 \(f_{i,j,k}\) 表示前 \(i\) 个字符,可以加入 \(j\) 个字符使得序列可以完全删除,\(k=0/1\) 表示当前是否能够删除。

则转移有:

  • \(f_{i+1,j,1}=f_{i,j,1}\times j\)
  • \(f_{i+1,j+1,0}=f_{i,j,1}\times (m-j)\)
  • \(f_{i+1,j,1}=f_{i,j,0}\times j\)
  • \(f_{i+1,j,0}=f_{i,j,0}\times (m-j)\)。此情况就是加入但无效果。
#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long

const int N = 3005, mod = 1e9 + 7;
int n, m, f[N][N][2], res;

signed main() {
	cin >> n >> m;
	f[0][0][1] = 1;
	_for(i, 0, n - 1) {
		_for(j, 0, i) {
			f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][1] * j % mod) % mod;
			f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][1] * (m - j) % mod) % mod;
			f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][0] * j % mod) % mod;
			f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][0] * (m - j) % mod) % mod;
		}
	}
	_for(i, 0, n) res = (res + f[n][i][1]) % mod;
	cout << res << endl; 
}

标签:NOIP,int,ed,tree,复习题,res,动态,dp,mod
From: https://www.cnblogs.com/stOtue/p/18414196

相关文章

  • 【Unity】创建动态的Tooltip
    需求说明文字内容动态变化;根据文字的内容自适应宽高;跟随鼠标移动;可以隐藏和展示;鼠标到达窗口边缘,tooltip停靠边缘可见;成果展示Scene部分查看UI相机和Canvas的设置注意将文字放在最左下角脚本部分TooltipScreenSpaceUI脚本绑定至TooltipScreenSpaceUI物体public......
  • 反射&动态代理
    1.反射1.1反射的概述:**专业的解释(了解一下):**是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意属性和方法;这种动态获取信息以及动态调用对象方法的功能称为Java语言的反射机制。**通俗的理解:(掌握)**......
  • springboot动态线程池
    1、配置文件新增每个线程池的基本参数配置thread-pool.user-thread.corePoolSize=1thread-pool.user-thread.maxPoolSize=1thread-pool.user-thread.keepAliveSeconds=120thread-pool.user-thread.queueCapacity=1thread-pool.school-thread.corePoolSize=2thread-pool.sch......
  • vue3/provider 和 inject实现跨组件动态数据传递。
    实现跨层传递在Vue中,provider和inject是一种用于实现依赖注入的高级特性,允许一个祖先组件向其所有子孙组件注入一个依赖,而不论组件层次有多深,并在起上下游关系成立的时间里始终生效。这在某些场景下非常有用,比如当你需要跨多个组件层级传递数据时。定义provide对象:在父组......
  • Java Server Page动态包含与重定向
    一、动态包含需求:我希望能够在我的页面中包含一个音频分析:在页面被请求的时候动态地包含另一个JSP页面或者静态资源(如HTML页面、图片等)的内容。假设我已经有一个名为audio.jsp的页面。当服务器处理包含<jsp:includepage="audio.jsp"/>的JSP页面时,它会将audio.jsp页面的......
  • Python中如何动态地执行代码
    在Python中,动态执行代码是一种强大的功能,它允许程序在运行时构建并执行字符串形式的代码。这种能力在多种场景下非常有用,比如开发交互式应用程序、构建代码模板、动态生成和执行函数等。Python提供了几种不同的方式来动态执行代码,包括使用exec()、eval()、compile()函数,以及通......
  • Java 中实现动态代理
    在Java中,动态代理(DynamicProxy)允许在运行时创建代理对象来处理方法调用,而不需要在编译时定义具体的实现类。Java的java.lang.reflect.Proxy类和java.lang.reflect.InvocationHandler接口是实现动态代理的关键。步骤:创建接口:定义一个接口,代理对象将会实现这个接口......
  • 《C++中动态数组的实现与探索》
    在C++编程中,动态数组是一种非常重要的数据结构,它能够根据实际需求在运行时动态地调整大小,为程序员提供了极大的灵活性。本文将深入探讨如何在C++中实现动态数组,包括使用内置数据结构和自定义实现的方法,同时分析其性能特点和应用场景。一、引言在编程过程中,我们经常会遇......
  • ARM-8 代码还原动态调试之 pstree 多个条件跳转
    402600: b9405360 ldr w0,[x27,#80]//w0=show_parents,调试确认为show_parents402604: f9400774 ldr x20,[x27,#8]//x20=list402608: 7100001f cmp w0,#0x0//show_parents?=040260c: b9401fe0 ldr w0,[sp,#28]//......
  • 转载:国产操作系统麒麟v10、UOS在线打开excel文件并动态赋值
    在实际的开发过程中,经常会遇到数据库中的数据填充到excel生成一份正式文件的功能,PageOffice客户端控件支持在线预览Excel文件时,通过Workbook对象来实现对Excel文件的数据填充功能,如果只是简单的填充一下数据,那么通过调用Sheet对象的openCell方法获取到Cell对象并赋值即可Java......