首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

DP进阶合集

编程知识
2024年07月28日 16:31

(ps:本集合为Star_F总结的dp进阶知识,持续更新~。 转载本文章需要联系我,否则视为侵权!!)

前置知识:线性dp,背包,树形dp,区间dp

内容预览:

  • 状压dp
  • 数位dp
  • dp优化(前缀和,单调队列,斜率优化)

1. 状压dp:

思路:如果题目中 \(n\) 的范围特别小(\(<=20\)) 大概率可以状压dp
状态:f[i][j]:考虑到前 \(i\) 个,且已考虑的集合为 \(j\) (j为二进制数,1表示考虑,0表示不考虑)
的集合
(辅助知识:位运算)

例题:

  • P1171 售货员的难题
    dp[i][j] 表示从起点到第j号点 且到达时状态恰好为i的最短路
    比较简单的状压dp,之间看代码吧:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int f[1<<20][20],w[20][20],n;
int main(){
	cin>>n;	
	memset(f,0x3f,sizeof f);
	f[1][0]=0;
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			cin>>w[i][j];
	for(int i=1;i<(1<<n);i+=2)   //枚举状态
		for(int j=0;j<n;j++){    //枚举下一步到达的点
			if(!((i >> j) & 1)) continue; 
			for(int k=0;k<n;k++){    枚举中介点
				if(j==k) continue;
				if(!(i>>k &1)) continue; 
				f[i][j]=min(f[i][j],f[i^(1<<j)][k]+w[k][j]);
			}
		}
	int minn=2e9;
	for(int i=0;i<=n-1;++i) minn=min(minn,f[(1<<n)-1][i]+w[i][0]);
	cout<<minn<<endl;
	return 0;
}
  • P1896 [SCOI2005] 互不侵犯
    思路:f[i][j][s]就表示在只考虑前i行时,在前i行(包括第i行)有且仅有s个国王,且第i行国王的情况是编号为j的状态时情况的总数。而k就代表第i-1行的国王情况的状态编号。
点击查看代码
	#include<cstdio>
	#include<iostream>
	#include<cstring>
	#include<cmath>
	#include<string>
	#include<algorithm>
	using namespace std;
	int sit[2000],gs[2000];
	int cnt=0;
	int n,yong;
	long long f[10][2000][100]={0};
	void dfs(int he,int sum,int node)//预处理出每一个状态
	{
	if(node>=n)//如果已经处理完毕(注意是大于等于)
	{
	sit[++cnt]=he;
	gs[cnt]=sum;
	return;//新建一个状态
	}
	dfs(he,sum,node+1);//不用第node个
	dfs(he+(1<<node),sum+1,node+2);//用第node个,此时node要加2,及跳过下一个格子
	}
	int main()
	{
	scanf("%d%d",&n,&yong);
	dfs(0,0,0);
	for(int i=1;i<=cnt;i++)f[1][i][gs[i]]=1;//第一层的所有状态均是有1种情况的
										 for(int i=2;i<=n;i++)
	for(int j=1;j<=cnt;j++)
						   for(int k=1;k<=cnt;k++)//枚举i、j、k
	{
	if(sit[j]&sit[k])continue;
	if((sit[j]<<1)&sit[k])continue;
	if(sit[j]&(sit[k]<<1))continue;//排除不合法国王情况
	for(int s=yong;s>=gs[j];s--)f[i][j][s]+=f[i-1][k][s-gs[j]];//枚举s,计算f[i][j][s]
	}
	long long ans=0;
	for(int i=1;i<=cnt;i++)ans+=f[n][i][yong];//统计最终答案,记得用long long
							   printf("%lld",ans);
							   return 0;
}

2. 数位dp:

以一个数的数位进行dp,一般为求一个区间满足某些条件的数
通常把区间改为\((1...r) - (1...l-1)\)

例题:

点击查看代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
    for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k <= 9; k ++ )
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if (!n) return 0;

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = -2;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = i == nums.size() - 1; j < x; j ++ )
            if (abs(j - last) >= 2)
                res += f[i + 1][j];

        if (abs(x - last) >= 2) last = x;
        else break;

        if (!i) res ++ ;
    }


    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];

    return res;
}

int main()
{
    init();

    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}

  • CF628D
    递归做法,枚举到那一位,现在的属性,有没有什么限制
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9+7;
ll m,d,a[2005],len,f[2005][2005];
char l[2005],r[2005];
ll dfs(int u,int sum,int yaoqiu){
	if(u>len) return sum==0?1:0;
	if(!yaoqiu&&f[u][sum]!=-1) return f[u][sum];
	ll tmp=0,maxx=yaoqiu==1?a[u]:9;
	if(u%2==1){
		for(int i=0;i<=maxx;i++)
			if(i!=d) tmp=(tmp+dfs(u+1,(sum*10+i)%m,yaoqiu&&(i==maxx)))%mod;
	}
	else{
		for(int i=0;i<=maxx;i++)
			if(i==d) tmp=(tmp+dfs(u+1,(sum*10+i)%m,yaoqiu&&(i==maxx)))%mod;
	}
	if(!yaoqiu) f[u][sum]=tmp;
	return tmp;
}
ll dp(char *s){
	memset(f,-1,sizeof(f)); 
	len=strlen(s+1);
	for(int i=1;i<=strlen(s+1);i++) a[i]=s[i]-'0';
	return dfs(1,0,1);
}
bool check(char *s){
    len=strlen(s+1);
    int x=0;
    for(int i=1;i<=len;i++){
        int y=s[i]-'0';
        x=(x*10+y)%m;
        if(i&1){
            if(y==d)
                return false;
        }
        else{
            if(y!=d)
                return false;
        }
    }
    return !x;
}
int main(){
	cin>>m>>d>>l+1>>r+1;
	cout<<(dp(r)-dp(l)+check(l)+mod)%mod;
    return 0;
}

3.dp优化:

From:https://www.cnblogs.com/fanrunze/p/18328535
本文地址: http://www.shuzixingkong.net/article/521
0评论
提交 加载更多评论
其他文章 简单网页制作
网页效果预览 这个网页包含图片,链接,字体设置,表格等 初学者最好手敲代码,更快熟悉元素和结构 完整的代码放在最后了 一:代码怎么变成网页 之前我们安装了xampp,启动xampp里的apache及sql 在xampp下找到htdocs目录 新建文件夹改名后缀为.php即可 将新建文件用记事本打开
简单网页制作 简单网页制作 简单网页制作
STM32F103 SPI详解及示例代码
SPI是嵌入式中使用比较广泛的协议之一,本文从该协议的原理入手对其进行了详细介绍,并结合STM32F103ZET主控芯片对其进行了说明,最后给出了两个实例代码demo供大家做参考。
STM32F103 SPI详解及示例代码 STM32F103 SPI详解及示例代码 STM32F103 SPI详解及示例代码
Vite本地构建:手写核心原理
前言 接上篇文章,我们了解到vite的本地构建原理主要是:启动一个 connect 服务器拦截由浏览器请求 ESM的请求。通过请求的路径找到目录下对应的文件做一下编译最终以 ESM的格式返回给浏览器。 基于这个核心思想,我们可以尝试来动手实现一下。 搭建静态服务器 基于koa搭建一个项目: 项目结构
Vite本地构建:手写核心原理 Vite本地构建:手写核心原理 Vite本地构建:手写核心原理
基于Hive的大数据分析系统
1.概述 在构建大数据分析系统的过程中,我们面对着海量、多源的数据挑战,如何有效地解决这些零散数据的分析问题一直是大数据领域研究的核心关注点。大数据分析处理平台作为应对这一挑战的利器,致力于整合当前主流的各种大数据处理分析框架和工具,以实现对数据的全面挖掘和深入分析。本篇博客笔者将为大家介绍如何构建
基于Hive的大数据分析系统 基于Hive的大数据分析系统 基于Hive的大数据分析系统
ComfyUI插件:ComfyUI Impact 节点(二)
前言: 学习ComfyUI是一场持久战,而 ComfyUI Impact 是一个庞大的模块节点库,内置许多非常实用且强大的功能节点 ,例如检测器、细节强化器、预览桥、通配符、Hook、图片发送器、图片接收器等等。通过这些节点的组合运用,我们可以实现的工作有很多,例如自动人脸检测和优化修复、区域增强、
ComfyUI插件:ComfyUI Impact 节点(二) ComfyUI插件:ComfyUI Impact 节点(二) ComfyUI插件:ComfyUI Impact 节点(二)
Jenkins如何使用CrumbIssuer防御CSRF攻击
1、CSRF(跨站请求伪造)概述 在讲解Jenkins的跨站请求伪造(CSRF)保护机制之前,让我们首先对CSRF这一安全威胁及其重要性进行简明扼要的概述。 1.1 CSRF(跨站请求伪造)的原理 CSRF(即跨站请求伪造)是指利用受害者尚未失效的身份认证信息、(cookie、会话等),诱骗其点击恶
Jenkins如何使用CrumbIssuer防御CSRF攻击 Jenkins如何使用CrumbIssuer防御CSRF攻击 Jenkins如何使用CrumbIssuer防御CSRF攻击
Nuxt.js 路由管理:useRouter 方法与路由中间件应用
title: Nuxt.js 路由管理:useRouter 方法与路由中间件应用 date: 2024/7/28 updated: 2024/7/28 author: cmdragon excerpt: 摘要:本文介绍了Nuxt 3中useRouter方法及其在路由管理和中间件应用中的功能。内容包括
Nuxt.js  路由管理:useRouter 方法与路由中间件应用 Nuxt.js  路由管理:useRouter 方法与路由中间件应用
设计模式:代理、装饰和适配器模式的区别
结构对比 讲实话,博主当初学习完整设计模式时,这三种设计模式单独摘哪一种都是十分清晰和明确的,但是随着模式种类的增加,在实际使用的时候竟然会出现恍惚,例如读开源代码时,遇到不以模式命名规范的代码时,一时难以说清具体是使用的这三种里的哪一种。 之所以会出现混淆的原因是,三种模式的实现都是基于面向接口这
设计模式:代理、装饰和适配器模式的区别 设计模式:代理、装饰和适配器模式的区别 设计模式:代理、装饰和适配器模式的区别