首页 > 其他分享 >关于 DP 的非常规优化

关于 DP 的非常规优化

时间:2024-11-09 22:07:47浏览次数:1  
标签:tmp 非常规 arr int son ++ vec 优化 DP

感觉这个东西就是玄学啊,考场上真的有人能想得出来嘛。(还是我太菜了qwq)

思想现在见到的有这几种:

  • 从 \(i\) 推到 \(i + 1\) 时状态改变的数量不会太多,直接继承可以优化。

  • 可能对答案有贡献的状态不会太多。即通过一些性质来消除掉冗余状态以保证时间复杂度。

ABC176F Brave CHAIN

容易有简单 \(O(n^3)\) \(\mathrm {DP}\):设 \(f_{i, a, b}\) 是前 \(3\times i + 2\) 个保留 \((a, b)\) 时的最大答案。有一下三类转移:

  • 不换卡:\(f_{i, a, b} = f_{i - 1, a, b} + [c = d = e]\)

  • 换一张:\(f_{i, a, c} = f_{i - 1, a, b} + [b = d = e]\)

  • 换两张:\(f_{i, c, d} = f_{i - 1, a, b} + [a = b = e]\)

当然有一些类似的不予考虑。我们发现其实没有多少状态被影响到了,若被影响到的多,原因也是 \(c = d = e\),于是猜测影响到的状态不多。接下来考虑什么样的状态 \(f_{i, a, b}\) 可能会被这三类转移分别更新。

对于第一种,显然对于任意 \(f_{i, a, b}\) 有没有被更新取决于 \([c = d = e]\),而这三者又是固定的,于是维护一个全局加标记即可。

对于第二种,被影响到的状态只有 \(c\) 这一列,若 \([b = d = e]\) 成立,此时转移过来的状态是固定的。若不满足,其实就是对于固定的 \(a\),让 \(f_{i, a, c}\) 更新为这一行的最大值,维护一下即可。

对于第三种,若满足 \([a = b = e]\),两边都是确定的。直接转移即可。若不满足,显然等价于更新为全局最大值,也是维护一下即可。

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

const int N = 2000 + 10;

int n, f[N][N], arr[N * 3];
void MAX(int& x, int y){if(x < y) x = y;}

struct opt{
	int k0, k1, val;
};
void upd(int a, int b, int w){
	MAX(f[a][b], w); MAX(f[a][0], w); MAX(f[0][0], w);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n; memset(f, -0x3f, sizeof f); int allsum = 0;
	for(int i = 1; i <= 3 * n; i++) cin >> arr[i];
	upd(arr[1], arr[2], 0); upd(arr[2], arr[1], 0);
	for(int i = 1; i < n; i++){
		queue<opt> Q; int c = arr[3 * i], d = arr[3 * i + 1], e = arr[3 * i + 2], ad = 0;
		// f[i][a][b]
		if(c == d && d == e) ad++, allsum++;
		// f[i][a][c], f[i][a][d], f[i][a][e]
		for(int a = 1; a <= n; a++){
			if(d == e) Q.push((opt){a, c, f[a][d] + 1});
			Q.push((opt){a, c, f[a][0]});
			if(c == e) Q.push((opt){a, d, f[a][c] + 1});
			Q.push((opt){a, d, f[a][0]});
			if(d == c) Q.push((opt){a, e, f[a][d] + 1});
			Q.push((opt){a, e, f[a][0]});
		}
		// f[i][c][d], f[i][c][e], f[i][d][e]
		Q.push((opt){c, d, f[e][e] + 1}); Q.push((opt){c, d, f[0][0]});
		Q.push((opt){c, e, f[d][d] + 1}); Q.push((opt){c, e, f[0][0]});
		Q.push((opt){d, e, f[c][c] + 1}); Q.push((opt){d, e, f[0][0]});
		// update
		while(!Q.empty()){
			opt ths = Q.front(); Q.pop(); 
			int a = ths.k0, b = ths.k1, w = ths.val - ad;
			upd(a, b, w); upd(b, a, w);
		}
	}
	int ans = 0;
	for(int a = 1; a <= n; a++){
		for(int b = 1; b <= n; b++){
			MAX(ans, f[a][b] + (a == b && b == arr[n * 3]));
		}
	}
	cout << ans + allsum;

	return 0;
}
/*
f[i][a][b] = f[i - 1][a][b] + [c = d = e]
f[i][a][c] = f[i - 1][a][b] + [b = d = e]
f[i][c][d] = f[i - 1][a][b] + [a = b = e]
*/

AGC007E Shik and Travel

非常厉害的一道题!

首先容易发现答案具有单调性,于是先通过二分答案 \(V\) 转化成为判定问题。

接下来注意到一条边只能走两次,其实就是限制了当进入一棵子树,必须先把里面的所有点经过之后才能离开这棵子树。也就是说,当处理到一颗子树时,需要把它的一颗子树处理完,然后从一个叶子到另一颗子树的叶子,再处理完这个子树,然后离开。

不难发现我们只需要知道两颗子树从 \(u\) 到第一个叶子的距离以及最后一个叶子到 \(u\) 的距离。于是容易设计出状态 \(f_{u, a, b}\) 表示是否有一种处理方案满足费用 \(\le V\),且 \(u\) 到第一个叶子的距离为 \(a\),最后一个叶子到 \(u\) 的距离为 \(b\)。状态转移就是

\[f_{u, a, b} = f_{ls, a - da, i - da} \& f_{rs, j - db, b - db} \& [i + j \le V] \]

但是想要再优化就没有那么简单了。首先需要注意到一个显然的但是容易被忽略的性质:若 \(x_1 \le x_2, y_1 \le y_2\),\(f_{x_2, y_2}\) 被 \(f_{x_1, x_2}\) 严格偏序,即没有用。于是我们可以将这些状态删掉,只记录有用的状态中值为 \(1\) 的,以减小时间复杂度。此时对于一个 \(u\),其有用的 \(f\) 值显然是满足 \(a\) 单调递增,\(b\) 单调递减。于是可以双指针合并一下两颗子树中的信息。

但是这样的时间复杂度?我们设节点 \(u\) 中储存的有用的状态数为 \(siz_u\)。一次转移产生的状态数上限是 \(2 \times \min(siz_{ls}, siz_{rs})\),不难发现这其实等价于一个启发式合并,于是时间复杂度为 \(O(n \log n)\)。

code:

qwq
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll, ll>
using namespace std;

const int N = 2e5 + 10;

int n, son[N][3];
ll dis[N][2];
vector<pir> f[N], g[N], vec[N];
ll lim;

void clrvec(vector<pir> &v){vector<pir> __qwq; swap(__qwq, v);}

void Merge_array(int u){
    int j = 0; vector<pir> tmp;
    for(int i = 0; i < f[u].size(); i++){
           while(j < g[u].size() && (g[u][j].first < f[u][i].first || (g[u][j].first == f[u][i].first && g[u][j].second < f[u][i].second))) tmp.push_back(g[u][j++]);
           tmp.push_back(f[u][i]);
    }
    while(j < g[u].size()) tmp.push_back(g[u][j++]);
    if(tmp.empty()) return;
    int ttt = 0; vec[u].push_back(tmp[0]);
    for(int i = 1; i < tmp.size(); i++){
            if(tmp[i].second < vec[u][ttt].second) ttt++, vec[u].push_back(tmp[i]); 
    }
}

void dfs(int u){
    if(!son[u][2]){ vec[u].push_back(make_pair(0ll, 0ll)); return;}
    for(int i = 0; i < 2; i++) dfs(son[u][i]);
    int ls = son[u][0], rs = son[u][1], j = 0, sum = dis[u][0] + dis[u][1];
    for(int i = 0; i < vec[ls].size(); i++){
           while(j < vec[rs].size() && vec[ls][i].second + vec[rs][j].first + sum <= lim) j++;
           if(j) f[u].push_back(make_pair(vec[ls][i].first + dis[u][0], vec[rs][j - 1].second + dis[u][1]));
    }
    swap(ls, rs); j = 0;
    for(int i = 0; i < vec[ls].size(); i++){
           while(j < vec[rs].size() && vec[ls][i].second + vec[rs][j].first + sum <= lim) j++;
           if(j) g[u].push_back(make_pair(vec[ls][i].first + dis[u][1], vec[rs][j - 1].second + dis[u][0]));
    }
    Merge_array(u); clrvec(f[u]); clrvec(g[u]);
    //cout << u << " " << vec[u].size() << " qwq" << "\n";
    //for(int i = 0; i < vec[u].size(); i++) cout << vec[u][i].first << " " << vec[u][i].second << "\n";
}


bool check(ll V){
       //cout << "\n" << V << "\n" << ":::" << "\n";
       for(int i = 1; i <= n; i++) clrvec(f[i]), clrvec(g[i]), clrvec(vec[i]);
       lim = V; dfs(1);
       return vec[1].size();
}

signed main(){
       ios::sync_with_stdio(0);
       cin.tie(0); cout.tie(0);
       cin >> n;
       for(int i = 2; i <= n; i++){
            int x, y; cin >> x >> y;
            son[x][son[x][2]] = i; dis[x][son[x][2]] = y; ++son[x][2];
       }
       ll l = 0, r = 3e10, ans = 3e10;
       while(l <= r){
            ll mid = (l + r >> 1);
            if(check(mid)) r = mid - 1, ans = mid;
            else l = mid + 1;
       }
       cout << ans;

       return 0;
}

也是学会使用 \(\rm vim\) 了qwq

标签:tmp,非常规,arr,int,son,++,vec,优化,DP
From: https://www.cnblogs.com/little-corn/p/18537382

相关文章

  • InDepth Guide to Denoising Diffusion Probabilistic Models DDPM:DDPM扩散概率模型去
    AnIn-DepthGuidetoDenoisingDiffusionProbabilisticModelsDDPM–TheorytoImplementation中文翻译:DDPM扩散概率模型去噪深度指南——理论到实现https://learnopencv.com/denoising-diffusion-probabilistic-models/#forward-diffusion-equationhttps://github.com/......
  • 优化布线拥塞
    Note:文章内容以Xilinx系列 FPGA进行讲解    随着设计规模的增大和复杂度的提升,布线拥塞成为常见的问题,尤其是在用UltraScaleFPGA或UltraScale+FPGA时,布线拥塞往往成为时序收敛的瓶颈,也成为编译时间过长的“罪魁祸首”。1、布线拥塞的三种类型    ......
  • 计算机网络 - UDP 协议
    定义UDP(UserDatagramProtocol)用户数据报协议:是一种无连接的数据传输协议,传输前不需要建立连接,没有复杂的协议优点是:首部开销小,不需要连接,机制简单,可以一对一,一对多,多对一通信,使用与直播、视频通话等业务领域缺点是:传输无序,不能保证消息一定送到,有丢包的问题报文如下UDP报......
  • 【论文系列】DDIM ---DDPM上的优化
    WhatDDIM是啥?DDIM(DenoisingDiffusionImplicitModels)是一种扩散模型的变体,旨在加速图像生成过程并保持生成质量。它是在DDPM(DenoisingDiffusionProbabilisticModels)的基础上发展出来的,提供了一种更高效的去噪采样过程,减少了采样所需的步骤数量。WhyDDIM提出了能干啥?DD......
  • 如何进行数据库连接池的参数优化?
    以下是进行数据库连接池参数优化的一些方法:一、确定合适的初始连接数:考虑因素:数据库的规模、应用程序的启动需求以及预期的初始负载。如果数据库规模较小且应用程序启动时对数据库的即时访问需求不高,可以将初始连接数设置得较少,比如3到5个;如果数据库较大或应用启动后很快......
  • atcoder DP做题笔记
    [ABC163E]ActiveInfants题意:给定长度为\(n(n\le2\times10^3)\)的序列\(a\),重排使得\(a_x\times|x-p_x|\)之和最大。独立完成。从大到小地考虑\(a_i\),贪心地使得\(|x-p_x|\)最大。那么\(p_x\)要么在最左,要么在最右。因此在左边和右边形成了一坨前/后缀,然后......
  • 六、MyBatis-Plus高级用法(1):最优化持久层开发
    一、MyBatis-Plus快速入门1.1简介课程版本:3.5.3.1MyBatis-Plus......
  • 浅谈单片机的gcc优化级别__以双音频信号发生器为例
    IDE:  CLionHOST: Windows11MinGW:x86_64-14.2.0-release-posix-seh-ucrt-rt_v12-rev0GCC: arm-gnu-toolchain-13.3.rel1-mingw-w64-i686-arm-none-eabi一、简介        gcc有多种优化级别,一般不选择的情况下,IDE默认是按照-Og或这-O2优化的。        ......
  • 空夜 [换根DP]
    空夜Description给定\(n\)个节点的树,每个点有点权\(a_i\),对于每个\(i\),求出\(\sum_{j}\lfloor\frac{a_i}{2^{dis(i,j)}}\rfloor\)。\(dis(i,j)\)表示\(i\)到\(j\)的树上最短路径。Solution对于每个\(i\)都要求答案,等价于求以\(i\)为根的树的答案,可以想到......
  • 计算机图形学论文 | 木工设计与制造计划的共同优化
    ......