Peter算法小课堂—线性dp

这篇具有很好参考价值的文章主要介绍了Peter算法小课堂—线性dp。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天,你读完这篇文章,普及组的动态规划已经可以秒了。

最长公共子序列

求两个数列的最长公共子序列(Longest Common Subsequence,LCS)的长度。

数列 X 和 Y 的最长公共子序列 Z,是指 Z 既是 X 的子序列,又是 Y 的子序列,而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。

状态定义

f[i][j]表示x[1]、x[2]……x[i]和y[1]、y[2]……y[j]的LCS

状态转移方程

若x[i]=y[j],f[i][j]=f[i-1][j-1]+1;

若x[i]!=y[j],f[i][j]=max(f[i-1][j],f[i][j-1]);

Peter算法小课堂—线性dp,CSP-J一等奖高分冲刺,动态规划,建模,算法,动态规划

大家可以用滚动数组试试

回文词

给定一个字符串,问至少需要增加多少个字符,才能把这个字符串变成回文词。一个字符串是回文词,是指从前往后看和从后往前看是一样的。比如:abcba、abccba、bcaacb都是回文词,但 abc 不是回文词。

这道题是前一道题的衍生。

假设给定的字符串为s,将s反转,得到t。那么,答案就是:s长度-s和t的LCS。这里就不给代码了

最长上升子序列

朴素解法

f[i]表示以i结尾的最长上升子序列的长度

按照倒数第二个选谁分类:

我们先扫描i号元素前的每个元素(正向),找出第一个比i号元素小的元素k号。①仍然选i号元素,f[i]。②选k号,f[k]+1

但是,这种解法时间复杂度为O(N^2),一但长度到200,就会扣分,我们这次就讨论O(nlog n)的算法。

优化解法

不升子序列最小划分数

我们用贪心解决这个问题。定义d[i]为第i条不升子序列的最后一个数,cnt代表有几个子序列

我们先扫描每个数字x[i],再枚举每一个子序列,判断是否能接在某个子序列后,如果不行,则新增一个序列即可。

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int n,i,j,d[N],x[N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>x[i];
	int cnt=0;
	for(i=0;i<n;i++){
		for(j=0;j<cnt;j++)
			if(d[j]>=x[i]) break;
		d[j]=x[i];
		if(j==cnt) cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

O(N^2)的算法,显然要优化

不妨试试二分

#include <bits/stdc++.h>
#define N 1005
#define INF 2e9
using namespace std;
int n,d[N],x[N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>x[i];
	fill(d,d+n,INF);
	for(i=0;i<n;i++)
		*lower_bound(d,d+n,x[i])=x[i];
	int cnt=lower_bound(d,d+n,INF)-d;
	cout<<cnt<<endl;
	return 0;
}

大家可能就纳闷了:这玩意和LIS有神马关系???

Dilworth反链

Peter算法小课堂—线性dp,CSP-J一等奖高分冲刺,动态规划,建模,算法,动态规划

LIS为最长子序列, 那么说明一定能找到LIS个数,从左往右是递增的。那么这些树一定不能放在同一组内,不然与不升矛盾。到目前为止,每个数单独为一组,已经开了LIS组了。说明任何一种满足要求的分组,组数都>=LIS。

这一下子,LIS算法就从O(N^2)降到了O(NlogN)

航线问题

Peter算法小课堂—线性dp,CSP-J一等奖高分冲刺,动态规划,建模,算法,动态规划

这道题是上一道题的衍生。

设第1行第i个点对应第2行第f[i]个点。假设i<j,则两条线(i,f[i])和(j,f[j])不相交的充要条件是f[i]<f[j],于是问题变为求f的LIS了,这里就不发代码了。

两个排列的LCS

Peter算法小课堂—线性dp,CSP-J一等奖高分冲刺,动态规划,建模,算法,动态规划

我们可以把两个排列作相同的置换。如p1:1 5 3 2 4变成1 2 3 4 5,即做置换5→2,2→4,4→5,

于是我们可以将p1置换成1 2 ……n,p2做相同的置换,则问题就变为LIS了,时间复杂度O(N^2)

摆花

原题链接:P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

我们可以把问题抽象化:有 n 个数(c1​,c2​,...,cn​),0⩽ci​⩽ai​,求有多少种方案数使

就变成经典dp了,Peter算法小课堂—线性dp,CSP-J一等奖高分冲刺,动态规划,建模,算法,动态规划

然后可以使用前缀和优化

乘积最大

原题链接:P1018 [NOIP2000 提高组] 乘积最大 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题,我只给代码,大家自己思考一下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[45][60];
string in;
int n,k;//n位数  k个乘号 
long long g[45];
long long cut(int l,int r){
    long long end = 0;
    for(int i = l;i <= r;i++)
        end = end * 10 + g[i];
    return end;
}
int main(){
    cin >> n >> k >> in;
    for(int i = 1;i <= n;i++)
        g[i] = in[i - 1] - '0';
    for(int i=1;i<=n;i++)
        f[i][0] = cut(1,i);
    for(int i = 2;i <= n;i++){ //枚举分割为前i位数字 
        for(int a = 1;a <= min(i-1,k);a++){ //枚举有几个乘号 
            for(int b = a;b < i;b++){ //在第几位放乘号 
                 f[i][a] = max(f[i][a],f[b][a-1] * cut(b + 1,i));
            }
        }
    }
    cout<<f[n][k];
    return 0;
}

反逆序对问题

给定 n,k,求在所有长度为 n的排列中,有多少排列的逆序对恰好为 k 。

给出表答(懒得打LateX)

Peter算法小课堂—线性dp,CSP-J一等奖高分冲刺,动态规划,建模,算法,动态规划

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

const int Maxn=10100;
const ll Mod=1e9+7;
int n,k;
ll f[Maxn],sm[Maxn];

int main(){
    scanf("%d%d",&n,&k);

    f[0]=1;
    for(int i=1;i<=n;i++){
        sm[0]=f[0];
        for(int j=1;j<=k;j++) sm[j]=(sm[j-1]+f[j])%Mod;
        for(int j=0;j<=k;j++){
            if(i>j) f[j]=sm[j];
            else f[j]=(sm[j]-sm[j-i]+Mod)%Mod;
        }
    }
    printf("%lld",f[k]);

    return 0;
}

今天的题目就是这么简单,祝大家早日AC

彩蛋

给定一个十进制整数 n,保证 n 的首位不为 00,你必须删除其中 d 个数字,使得留下的数字最大。请输出留下的最大数。文章来源地址https://www.toymoban.com/news/detail-855980.html

到了这里,关于Peter算法小课堂—线性dp的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Peter算法小课堂—自定义容器

    这个算法复杂度为O(nm),显然有更快的算法  但是,这样写有个很危险的错误,如下 运行出来是这样的,  原因很简单,因为set的功能是排序、去重,然而结构体排序要加上“.\\\",所以会报错 改后代码, 那么,回到原题,代码该怎么写呢? 当然这个代码也有高级版,但要升

    2024年02月04日
    浏览(38)
  • Peter算法小课堂—正整数拆分

    大家可能会想:正整数拆分谁不会啊,2年级就会了,为啥要学啊 正整数拆分有好几种,这里我们列举两种讲。 我们看着第一幅图,头向左转90°,记住你看到的图,再来看第二幅图,你会惊奇的发现:第一幅图向左转90°就变成了第二幅图!因此,我们做出来一道题,就能推

    2024年02月07日
    浏览(42)
  • Peter算法小课堂—拓扑排序与最小生成树

    讲拓扑排序前,我们要先了解什么是DAG树。所谓DAG树,就是指“有向无环图”。请判断下列图是否是DAG图 第一幅图,它不是DAG图,因为它形成了一个环。第二幅图,它也不是DAG图,因为它没有方向。第三幅图才叫真正的DAG图(DAG图不一定联通)。 那什么叫DAG图的拓扑排序呢

    2024年01月21日
    浏览(48)
  • [CSP-J 2022] 解密

    大家好,今天我来解题[CSP-J 2022] 解密 题目来源链接 题目描述 给定一个正整数 k k k ,有 k k k 次询问,每次给定三个正整数 n i , e i , d i n_i, e_i, d_i n i ​ , e i ​ , d i ​ ,求两个正整数 p i , q i p_i, q_i p i ​ , q i ​ ,使 n i = p i × q i n_i = p_i times q_i n i ​ = p i ​ × q i ​ 、 e

    2024年02月08日
    浏览(48)
  • 2023CSP-J题解

    烦死了,这次CSP考的真的垃圾,犯了好多低级错误。 小 Y 的桌子上放着 n n n 个苹果从左到右排成一列,编号为从 1 1 1 到 n n n 。 小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。 每天在拿的时候,小苞都是从左侧第 1 1 1 个苹果开始、每隔 2 2 2 个苹果拿走 1 1 1 个苹果。

    2024年02月08日
    浏览(55)
  • 备考CSP-J—贪心

    额……既然是备考,那么一定要动脑筋,一共5题,大家好好思考一下。 一:P1250 种树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 二:P1020 [NOIP1999 提高组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)  三:P1230 智力大冲浪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

    2024年01月25日
    浏览(50)
  • 2022CSP-J2题解

    今天(2022,10,29), C S P − J S CSP-JS C S P − J S 第二轮成功举办, 虽然大部分省市疫情取消 本蒟蒻今天有幸参加CSP,特发入门组题解 小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a a a 和 b b b ,求 a b a^b a b 的值是多少。 a b a^b a b 即 b b b 个 a a a 相乘

    2023年04月08日
    浏览(84)
  • 2022 CSP-J 复赛题解

    【题目描述】 小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a 和 b ,求 a b 的值是多少。 a b 即 b 个 a 相乘的值,例如 23 即为 3 个 2 相乘,结果为 2 × 2 × 2 = 8。 “简单!”小文心想,同时很快就写出了一份程序,可是测试时却出现了错误。 小文

    2024年02月07日
    浏览(63)
  • 2022CSP-J 题解[完整版]

    “西西弗”的脑子是被宇宙射线影响了吗,造的题目我都写到睡着了…… 题目描述 小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a a a 和 b b b ,求 a b a^b a b 的值是多少。 a b a^b a b 即 b b b 个 a a a 相乘的值,例如 2 3 2^3 2 3 即为 3 3 3 个 2 2 2 相乘,

    2024年02月10日
    浏览(70)
  • CSP-J/S——初赛复习(未完)

    废话不多说,马上开始。 还是说一点吧:个人认为《信息学奥赛一本通——初赛篇》里有些废话,不够精炼,CSP-J/S重点不够突出, 本人想将知识整理起来,并总结提炼 ,以便备考以及复习。 本文参考了《信息学奥赛一本通——初赛篇》,是对它一个整理、总结与简化。

    2024年02月10日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包