DP专项训练

2024-06-15 09:28
文章标签 训练 dp 专项

本文主要是介绍DP专项训练，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题

来源:P3609 [USACO17JAN] Hoof, Paper, Scissor G

题意

给你n个蹄子/剪刀/布，在你没改变前出法均相同，可以改k次之后最多的相同的局数有多少。

做法

线性DP

因为手势用的字符表示，为方便可以转换为数字

void calc(int i,char a){if(a=='H'){d[i]=1;}else if(a=='P'){d[i]=2;}else{d[i]=3;}
}

我们还可以写一个check函数，来判断当前出的手势是否可以赢奶牛出的手势

bool check(int x,int y){if((x==1&&y==2)||(x==2&&y==3)||(x==3&&y==1)){return true;}return false;
}

约定m为题中的k

分析

  1. 状态定义:f(i,j,k):前i次中改变j次，且第i次手势为k的最大获胜次数
  2. 状态转移: 不改:f(i,j,k)=f(i-1,j,k)+g
    改:f(i,j,k)=max(f(i-1,j,k)+g,f(i-1,j-1,l)+g); 1<=i<=n,1<=j<=m,1<=k,l<=3 g=check(k,s)，s为当前奶牛出的手势 l指除k意外的两种手势

结果: ans=max{f(n,m,l)},l为三种手势

时间复杂度

将字符转为数字为O(n)dp中:遍历1到n为O(n)遍历改变情况为O(m)遍历一遍上一次的手势与当前手势为3*3check函数为O(1)时间复杂度约为(9mn)总时间复杂度约为O(9mn)

代码

这里采用记忆化搜索

#include<iostream>
using namespace std;
int n,m;
const int N=100010;
char s[N];
int d[N];
int f[N][4][110];
void calc(int i,char a){if(a=='H'){d[i]=1;}else if(a=='P'){d[i]=2;}else{d[i]=3;}
}
bool check(int x,int y){if((x==1&&y==2)||(x==2&&y==3)||(x==3&&y==1)){return true;}return false;
}
int dfs(int i,int j,int k){if(f[i][j][k]){return f[i][j][k];}if(i>n){return 0;}int l=check(d[i],j);int x=dfs(i+1,j,k),y=-0x3f3f3f3f;if(k>0){if(j==1){y=max(dfs(i+1,2,k-1),dfs(i+1,3,k-1));}else if(j==2){y=max(dfs(i+1,1,k-1),dfs(i+1,3,k-1));}else{y=max(dfs(i+1,1,k-1),dfs(i+1,2,k-1));}}return f[i][j][k]=max(x,y)+l;
}
int main(){freopen("hps.in","r",stdin);freopen("hps.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];calc(i,s[i]);}int a=dfs(1,1,m);int b=dfs(1,2,m);int c=dfs(1,3,m);cout<<max(a,max(b,c));
}

第二题

来源:P3140 [USACO16FEB] Circular Barn Revisited G

题意:

即求满足给定序列所需要的最小总代价

做法:

考虑线性DP
因为仓库是圆形的，即构成了一个环 所以我们应破环成链

约定m为开门数，即文中给出的k

分析

  1. 状态定义：f(i,k):开启第i扇门时共开了k扇门的最小总路程

  2. 状态计算：f(i,k)=min{f(j-1,k)+g(i,j)};

           1<=i<=n,1<=j<=i,1<=k<=m由于我们破环成链，所以应以1..n为开头依次遍历l指开头，r指结尾g(i,j)指由i门转移到j门的路程和

为了节省时间复杂度,g(i,j)可以预处理

结果：ans=min{f(l,m)}; 1<=l<=n;

时间复杂度

瓶颈在dp部分
以1..n为开头依次遍历为O(n)
计算f(i,k)为三重循环，时间复杂度为O(mn^2)
总时间复杂度约为O(mn^3)
注意：不开long long见祖宗

代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=210;
int n,m;
int a[N];
int f[N][8],g[N][N];
signed main(){cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);a[i+n]=a[i];}for(int i=1;i<=2*n;i++){int x=0;int d=min(i+n-1,2*n);for(int j=i+1;j<=d;j++){x=x+(j-i)*a[j];g[i][j]=x;}}//预处理g数组int ans=1e18;for(int l=1;l<=n;l++){//遍历开头memset(f,0x3f,sizeof f);f[l-1][0]=0;//初始化f数组int r=l+n-1;for(int i=l;i<=r;i++){for(int j=1;j<=m;j++){for(int k=l;k<i;k++){f[i][j]=min(f[i][j],f[k-1][j-1]+g[k][i]);//状态转移}}}ans=min(ans,f[r][m]);}cout<<ans;
}

第三题

来源:P5424 [USACO19OPEN] Snakes G

题意:

将一个长为n的区间分为最多分为 (k+1) 个子区间,每个子区间的代价为 (区间最大值*长度-区间和) ,求最小代价

约定m=k+1

做法:

分段式线性dp

分析

  1. 状态定义:f(i,j):将前i个数分为j段时，所需要的最小代价

  2. 状态转移:f(i,j)=min{f(k-1,j)+(g(k,i)*(i-k+1)-sum(k,i))}

       1<=i<=n,1<=j<=i,1<=k<=m意思是:将前(k-1)个数分为(j-1)段,让k到i为一段g(k,i)为区间最大值，sum(k,i)为区间和这两个数组可以预处理

结果:ans=f(n,m)

时间复杂度

预处理 sum() ,g() 可以在O(n^2)的时间中求得DP部分除计算代价的地方不同以外，其他地方都与分段DP的模板相同
时间复杂度约为O(mn^2)总时间复杂度约为O(mn^2)

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N=410;
int f[N][N],d[N][N];
int n,m,a[N];
int sum[N][N];
signed main(){cin>>n>>m;m++;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}memset(f,-1,sizeof f);for(int i=1;i<=n;i++){int ans=0;for(int j=i;j<=n;j++){ans=max(ans,a[j]);d[i][j]=ans;sum[i][j]=sum[i][j-1]+a[j];}}memset(f,0x3f,sizeof f);f[0][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=1;k<=i;k++){f[i][j]=min(f[i][j],f[k-1][j-1]+(d[k][i]*(i-k+1)-sum[k][i]));}}}cout<<f[n][m];
}

第四题

来源:UVA11584 Partitioning by Palindromes

题意

当一个字符串正序和反序是完全相同时，我们称之为“回文串”,例如“racecar”就是一个回文串，而“fastcar”就不是
现在给一个字符串s，把它分割成若干个互不相交的回文子串，求分割的回文子串的最少个数

判断是否为回文串可以写一个 check() 函数

bool check(int l,int r){for(int i=l,j=r;i<=j;i++,j--){if(s[i]!=s[j]){return 0;}}return 1;
}

做法:

分段式线性DP

分析:

  1. 状态定义:f(i):由 1..i 的字符串中，最少可划分为多少个回文串

  2. 状态转移:f(i)=min{f(j-1)+1}

       1<=i<=n,1<=j<=i意思为:当满足check(j,i)(即满足 j..i 的字符串为回文串)时,将 1..j-1 的字符串划分为最少回文串数，并加上该串，与f(i)取最小值

结果: ans = f(n)

时间复杂度:

主要是dp部分，时间复杂度为O(n^3)，较高可以设一个p(i,j),判断由 i..j 的字符串是否为回文串
O(n^2)的时间预处理出所有p(i,j)，并O(n^2)的时间dp
可以自行了解

代码

#include<iostream>
#include<cstring>
using namespace std;
int t;
const int N=1010;
char s[N];
int f[N];
bool check(int l,int r){for(int i=l,j=r;i<=j;i++,j--){if(s[i]!=s[j]){return 0;}}return 1;
}
int main(){cin>>t;while(t--){memset(f,0x3f,sizeof f);scanf("%s",(s+1));int x=strlen(s+1);f[0]=0;for(int i=1;i<=x;i++){for(int j=1;j<=i;j++){if(check(j,i)){f[i]=min(f[j-1]+1,f[i]);}}}cout<<f[x]<<endl;}
}

第五题

来源:UVA11400 Lighting System Design

题意

你的任务是设计一个照明系统，一共有n（n<=1000)种灯泡可供选择,不同种类的灯泡必须用不同的电源，同一种灯泡则可以用一个
输入为一个n，以下n行，每行四个数值，代表电压V，电源费用K，每个灯泡费用C，所需灯泡数量L。n=0为结束标志

做法:

分段式线性dp

首先明确一个性质: 如果当前灯泡不如另外某种的灯泡，那么这类灯泡应全部换成其他比它优的灯泡 否则全部不换

因为只有电压比当前灯泡电压大的灯泡才能将当前灯泡换成该灯泡 所以我们应对灯泡按电压大小排序

分析

  1. 状态定义:f(i):前i种灯泡在进行操作后的最小总成本

  2. 状态转移:f(i)=min{f(j-1)+wb(i)+wc(i)*(sum(i)-sum(j-1))}

       1<=i<=n,1<=j<=i意思是:将 j..i 的灯泡类型全换成第i种，并加上前 j-1 种灯泡在操作后的最小成本，与f(i)取minwc(i)*(sum(i)-sum(j-1)) 指换后的成本其中:sum指灯泡数量的前缀和

结果: ans = f(n)

时间复杂度

排序为O(nlogn)
预处理前缀和为O(n)
dp套分段dp板子即可,复杂度为O(n^2)总时间复杂度约为O(n^2)

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int n;
const int N=1010;
struct node{int a,b,c,d;
}w[N];
int f[N],sum[N];
bool cmp(node a,node b){return a.a<b.a;
}
signed main(){while(cin>>n,n){memset(f,0x3f,sizeof f);memset(sum,0,sizeof sum);for(int i=1;i<=n;i++){cin>>w[i].a>>w[i].b>>w[i].c>>w[i].d;}sort(w+1,w+n+1,cmp);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+w[i].d;}f[0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){f[i]=min(f[i],f[j-1]+w[i].b+w[i].c*(sum[i]-sum[j-1]));}}cout<<f[n]<<endl;}
}

第六题

来源:P5924 [IOI2004] Phidias 菲迪亚斯神

题意

为了这座雕像他需要大小为 W1*H1,W2*H2...Wn*Hn​ 的矩形大理石板最近菲迪亚斯获得一块矩形大理石块。菲迪亚斯想把这块石板切成所需要的大小石板或是石板所切割出的部分都可以由垂直(或水平)方向纵贯(或是横贯)加以切割到底成为两块矩形石板,同时切割出的这两块矩形石板都必须具有整数的宽度与高度石板只能以此种方法加以切割，同时石板不能粘合成较大石板因为石板具有花纹，所以石板也不能旋转菲迪亚斯想知道如何切割最初的石板，才能让所产生的废料最少

设整个长方形成为W,宽为H

约定a[]为w[],b[]为h[]

做法

记忆化搜索

分析

  1. 状态定义:dfs(i,j):切割长为i,宽为j的长方形所浪费的最小值

  2. 状态转移:dfs(i,j)=min{min(dfs(i,j-b(k))+dfs(i-a[k],b(k)),dfs(i-a(k),j)+dfs(a(k),j-b(k)))}

        1<=i<=W,1<=j<=H,1<=k<=n可知:a(k)<=i,b(k)<=j其中:dfs(i,j-b(k))+dfs(i-a[k],b(k))为竖着切dfs(i-a(k),j)+dfs(a(k),j-b(k)))为横着切因为是记忆化搜索，所以每搜完一个状态就记录它的最小值f(i,j)初始值(搜索内)为i*j,及最多将整个长方形都浪费，后面挨个挨个取min注意f要全部初始化为-1(搜索外),因为有可能可以不浪费

结果:ans=dfs(W,H)

时间复杂度

因为记忆化搜索每个状态只会被搜一遍 所以最多搜W*H种状态

总时间复杂度约为O(W*H)

代码

#include<iostream>
#include<cstring>
using namespace std;
int w,h,n;
const int N=1010;
int a[N],b[N];
int f[N][N];
int dfs(int i,int j){if(f[i][j]!=-1){return f[i][j];}int res=i*j;for(int k=1;k<=n;k++){if(a[k]>i||b[k]>j){continue;}int x1=dfs(i,j-b[k])+dfs(i-a[k],b[k]);int x2=dfs(i-a[k],j)+dfs(a[k],j-b[k]);int cnt=min(x1,x2);res=min(res,cnt);}return f[i][j]=res;
}
int main(){memset(f,-1,sizeof f);cin>>w>>h>>n;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);}cout<<dfs(w,h);
}

第七题

来源:P4267 [USACO18FEB] Taming the Herd G

题意

农夫想要知道从他开始记录以来发生过多少次出逃。但是，他怀疑奶牛们篡改了它的记录，现在他所确定的只有他是从发生出逃的某一天开始记录的。
请帮助他求出，对于每个从他开始记录以来可能发生的出逃次数，他被篡改了的记录条数的最小值

约定m=n,即可能的出逃最大次数

做法

仍然是分段式线性DP

分析

  1. 状态定义:f(i,j):前i天中，出逃j次记录的与给定序列不同的最小数目

  2. 状态转移:f(i,j)=min{f(k-1,j-1)+g(k,i)}

       1<=i<=n,1<=j<=i,1<=k<=i因为前i天中最多出逃i次，所以j<=i(但设为j<=m也没关系)意思是:前 (k-1) 天出逃 (j-1) 次(且第k天出逃),一直到第i天再出逃的最小不同数量，与f(i,j)取min唯一与模板不同的是g(k,i)g(k,i)表示在第k天开始出逃,到第i天时有多少个不同的记录条数可以预处理得到

结果:ans=f(n,i),1<=i<=n

时间复杂度

预处理g()约为O(n^2) dp约为O(n^3)

总时间复杂度约为O(n^3)

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int n;
int a[N];
int f[N][N];
int g[N][N];
int main(){memset(f,0x3f,sizeof f);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){g[i][j]=g[i][j-1]+(a[j]!=(j-i));}}f[0][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//n可改为i,降低时间for(int k=1;k<=i;k++){f[i][j]=min(f[i][j],f[k-1][j-1]+g[k][i]);}}}for(int i=1;i<=n;i++){cout<<f[n][i]<<endl;}
}

第八题

来源:牛客假日团队赛54-A

题意

在Farmer John最喜欢的节日里，他想要给他的朋友们赠送一些礼物
由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而Farmer John即将得到这一教训Farmer John的N头奶牛（1≤N≤10000）排成一行，方便起见依次编号为1…N。奶牛i的包装礼物的技能水平为si
她们的技能水平可能参差不齐，所以FJ决定把她的奶牛们分成小组。每一组可以包含任意不超过K头的连续的奶牛（1≤K≤1000),并且一头奶牛不能属于多于一个小组由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平请帮助FJ求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值

做法

还是分段式线性DP

分析

  1. 状态定义:f(i):前i头牛中,分组后可取到的最高技术和

  2. 状态转移:f(i)=min{f(j-1)+w(i,i-j+1)*(i-j+1)}

       1<=i<=n,d<=j<=i其中:d为max(1,i-k+1)含义就不用多说了w(i,x)指以i为结尾，取第 i-x+1...i 的最大值同样预处理

结果:ans=f(n)

时间复杂度

易得:约为O(nm)

代码

#include<iostream>
using namespace std;
const int N=10010;
int f[N];
int n,a[N],k;
int w[N][1010];
int main(){freopen("teamwork.in","r",stdin);freopen("teamwork.out","w",stdout);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){int d=max(1,i-k+1),ans=0;for(int j=i;j>=d;j--){ans=max(ans,a[j]);w[i][i-j+1]=ans;}}for(int i=1;i<=n;i++){int d=max(1,i-k+1);for(int j=d;j<=i;j++){f[i]=max(f[i],f[j-1]+w[i][i-j+1]*(i-j+1));}}cout<<f[n];
}

这篇关于DP专项训练的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1063059。

相关文章

YOLO v3 训练速度慢的问题

YOLO v3 训练速度慢的问题

一天一夜出了两个模型，仅仅迭代了200次   原因：编译之前没有将Makefile 文件里的GPU设置为1，编译的是CPU版本，必须训练慢   解决方案： make clean  vim Makefile make   再次训练 速度快了，5分钟迭代了500次
阅读更多...
将一维机械振动信号构造为训练集和测试集（Python）

将一维机械振动信号构造为训练集和测试集（Python）

从如下链接中下载轴承数据集。 https://www.sciencedirect.com/science/article/pii/S2352340918314124 import numpy as npimport scipy.io as sioimport matplotlib.pyplot as pltimport statistics as statsimport pandas
阅读更多...
6月21日训练 (东北林业大学)（个人题解）

6月21日训练 (东北林业大学)（个人题解）

前言：   这次训练是大一大二一起参加的训练，总体来说难度是有的，我和队友在比赛时间内就写出了四道题，之后陆陆续续又补了了三道题，还有一道题看了学长题解后感觉有点超出我的能力范围了，就留给以后的自己吧。话不多说，上正文。 正文：   Problem:A 幸运数字： #include <bits/stdc++.h>using namespace std;int sum,ans;in
阅读更多...
【教师资格证考试综合素质——法律专项】学生伤害事故处理办法以及未成人犯罪法笔记相关练习题

【教师资格证考试综合素质——法律专项】学生伤害事故处理办法以及未成人犯罪法笔记相关练习题

目录 《学生伤害事故处理办法》 第一章 总 则 第二章 事故与责任 （谁有错，谁担责） 第三章  事故处理程序 第四章 事故损害的赔偿 第五章 事故责任者的处理 第六章 附 则 《中华人民共和国预防未成人犯罪法》 第一章 总 则 第二章 预防犯罪的教育 第三章 对不良行为的干预 第四章 对严重不良行为的矫治 第五章 对重新犯罪的预防 第六章法律责任 第七章 附 则
阅读更多...
上海邀请赛 A题目 HDU 5236（dp）

上海邀请赛 A题目 HDU 5236（dp）

先求出没有ctrl+s的时候构造长度为i的期望f[i] 。然后枚举保存的次数，求出最小即可。 #include<cstdio>#include<cstdio>#include<cmath>#include<queue>#include<stack>#include<string>#include<cstring>#include<iostream>#include<map>
阅读更多...
poj 3160 Father Christmas flymouse 强连通+dp

poj 3160 Father Christmas flymouse 强连通+dp

首先我们可以确定的是，对于val值小于0的节点都变成0.   假设一个集合内2个房间都能任意到达，那么我就可以吧集合内的所有点的价值都取到，并且可以达到任一点。实际上集合内的每个点是相同的，这样的集合就是一个强连通分量。 那么我们就可以用tarjin算法进行强连通缩点， 最后形成一个dag的图。在dag的图上面进行dp。可以先用拓扑排序后dp。或者建反响边记忆化搜索 。 VIEW
阅读更多...
秋招突击——6/22——复习{区间DP——加分二叉树，背包问题——买书}——新作{移除元素、实现strStr（）}

秋招突击——6/22——复习{区间DP——加分二叉树，背包问题——买书}——新作{移除元素、实现strStr（）}

文章目录 引言复习区间DP——加分二叉树个人实现 背包问题——买书个人实现参考实现 新作移除元素个人实现参考思路 找出字符串中第一个匹配项的下标个人实现参考实现 总结 引言 今天做了一个噩梦，然后流了一身汗，然后没起来，九点多才起床背书。十点钟才开始把昨天那道题题目过一遍，然后十一点才开始复习题目，为了不耽误下午的时间，所以这里的就单纯做已经做过的题目，主打一个有量，不在学
阅读更多...
国产AI算力训练大模型技术实践

国产AI算力训练大模型技术实践

&nbsp;&nbsp; ChatGPT引领AI大模型热潮，国内外模型如雨后春笋，掀起新一轮科技浪潮。然而，国内大模型研发推广亦面临不小挑战。面对机遇与挑战，我们需保持清醒，持续推进技术创新与应用落地。 为应对挑战，我们需从战略高度全面规划大模型的研发与运营，利用我们的制度优势，集中资源攻坚克难。通过加强顶层设计，统一规划，并加大政策与资源的扶持，我们必将推动中国人工智能实现从追赶者到
阅读更多...
预训练是什么？

预训练是什么？

预训练是什么？ 图像领域的预训练 在介绍图像领域的预训练之前，我们首先介绍下卷积神经网络（CNN），CNN 一般用于图片分类任务，并且CNN 由多个层级结构组成，不同层学到的图像特征也不同，越浅的层学到的特征越通用（横竖撇捺），越深的层学到的特征和具体任务的关联性越强（人脸-人脸轮廓、汽车-汽车轮廓） 由此，当领导给我们一个任务：阿猫、阿狗、阿虎的图片各十张，然后让我们设计一个深度神经网
阅读更多...
动态规划DP--斐波那契数、爬楼梯、使用最小花费爬楼梯等示例代码

动态规划DP--斐波那契数、爬楼梯、使用最小花费爬楼梯等示例代码

动态规划DP 文章目录 动态规划DP509. 斐波那契数70. 爬楼梯746. 使用最小花费爬楼梯62. 不同路径63. 不同路径II343.整数拆分 509. 斐波那契数 509. 斐波那契数 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) =
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2