文章目录
一、函数题
二、编程题
一、编程题
1.租用游艇问题
长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。
输入格式:
第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。
输出格式:
输出从游艇出租站1 到游艇出租站n所需的最少租金。
#include<bits/stdc++.h>
using namespace std;
int a[500][500];
int dp[500];
int main()
{
int n;cin>>n;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
cin>>a[i][j];
memset(dp,0x3f,sizeof dp);
dp[1]=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
dp[j]=min(dp[j],dp[i]+a[i][j]);
cout<<dp[n]<<endl;
}2.矩阵链相乘问题
矩阵的乘法定义如下：设A是m×p的矩阵，B是p×n的矩阵，则A与B的乘积为m×n的矩阵，记作C=AB，其中，矩阵C中的第i行第j列元素cij可以表示为：cij=Σk=1paik×bkj=ai1b1j+ai2b2j+⋯+aipbpj.
当多个矩阵相乘时，采用不同的计算顺序所需的乘法次数不相同。例如，A是50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵，
计算ABC有两种方式：(AB)C和A(BC)，前一种需要15000次乘法计算，后一种则只需3500次。
设A1,A2,...,An为矩阵序列，Ai是阶为Pi−1∗Pi的矩阵(1≤i≤n)。试确定矩阵的乘法顺序，使得计算A1A2...An过程中元素相乘的总次数最少。
输入格式:
每个输入文件为一个测试用例，每个测试用例的第一行给出一个正整数n(1≤n≤100)，表示一共有n个矩阵A1,A2,...,An，第二行给出n+1个整数P0,P1...Pn，以空格分隔，其中1≤Pi≤100(0≤i≤n)，第i个矩阵Ai是阶为Pi−1∗Pi的矩阵。
输出格式:
获得上述矩阵的乘积，所需的最少乘法次数
#include<bits/stdc++.h>
using namespace std;
const int N=2000;
int dp[N][N];
int a[N];
int main()
{
int n;cin>>n;
memset(dp,0x3f,sizeof dp);
for(int i=0;i<=n;i++)cin>>a[i],dp[i][i]=0;
for(int len=2;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+a[l-1]*a[k]*a[r]);
}
}
cout<<dp[1][n]<<endl;
}3.字母表
我们定义一个小写字符串是“按字母表的”，当且仅当它删除掉一些字符后，可以变为”abcdefghijklmnopqrstuvwxyz”。
给定一个长度为n的小写字母字符串，至少插入多少个字符才能使其变成“按字母表的”。
输入格式:
输入第一行为一个整数T（1<=T<=100），代表测试数据的组数，随后T行，每行都是由小写字母'a'-'z'组成的一串字符s (1=<|n|<=50)。
输出格式:
输出为了让s变成“按字母表的”，至少要插入的字符个数，每组输出占一行。
#include<bits/stdc++.h>
using namespace std;
int dp[100];
int main()
{
int t;cin>>t;
while(t--)
{
string s;cin>>s;int n=s.size();
int a[100]={0};
for(int i=0;i<100;i++)dp[i]=1;
for(int i=0;i<n;i++)a[i+1]=s[i]-'a';
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
}
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<26-ans<<endl;
}
}4.小H分糖果
小H来到一个小学分糖果，小学生们很听话，站成一排等着分糖果，小H将根据每个人的上次考试分数给一定的糖果，规则如下。
- 每个人都有自己分数ai，代表上次考试成绩。
- 每个人都至少有一颗糖。
- 如果两个人相邻，分数高的一定比分数低的糖果多
然而小H经费有限，他想知道最少需要多少糖果。
输入格式:
输入第一行包括一个整数n(1≤n≤105)。
接下来n行，每行1个整数ai(1≤ai≤105)表示站在第i位的人的分数。
输出格式:
输出最少需要多少糖果
#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int a[N],b[N];
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++)
{
if(a[i+1]>a[i])b[i+1]=b[i]+1;
}
for(int i=n;i>1;i--)
{
if(a[i-1]>a[i])b[i-1]=max(b[i-1],b[i]+1);
}
long long ans=0;
for(int i=1;i<=n;i++)
ans+=b[i];
cout<<ans+n<<endl;
}5.运动会
T公司的员工层级关系可以表示成一棵树，员工X是员工Y的直接领导，则在树中X是Y的父结点。公司拟组织一场运动会，但为了避免尴尬，每个员工都不想与自己的直接领导一起参赛。假定每个员工都对应一个权重（领导的权重不一定比下属大），请你编写程序，邀请若干员工参赛，使得参赛人员的总权重和最大。
输入格式:
第一行一个正整数n，表示公司的员工人数，员工编号为1...n，n不超过3000。
接下来n行，每行1个整数，表示每个员工的权重，值域为[−27,27)。
接下来n-1行，每行为两个空格间隔的整数X和Y，表示Y是X的直接领导。
输出格式:
输出为一个整数，表示参赛员工的最大权重之和。
#include<bits/stdc++.h>
using namespace std;
const int N=3010;
vector<int> a[N];
int root=0,w[N],b[N];
int no[N],yes[N];
void dfs(int u)
{
if(a[u].empty())
{
yes[u]=w[u];
return;
}yes[u]=w[u];
for(int i=0;i<a[u].size();i++)
{
dfs(a[u][i]);
yes[u]+=no[a[u][i]];
no[u]+=max(yes[a[u][i]],no[a[u][i]]);
}
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<n;i++)
{
int x,y;cin>>x>>y;
a[y].push_back(x);b[x]=y;
}
for(int i=1;i<=n;i++)
{
if(b[i]==0)
root=i;
}
//cout<<root<<endl;
dfs(root);
cout<<max(no[root],yes[root]);
}
6.0-1背包
给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入：
第一行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
#include<bits/stdc++.h>
using namespace std;
int w[200],v[200],dp[1010];
int main()
{
int n,c;cin>>n>>c;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)
for(int j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout<<dp[c];
}7.最长公共子序列长度
求两个字符串的最长公共子序列长度。
输入格式:
输入长度≤100的两个字符串。
输出格式:
输出两个字符串的最长公共子序列长度。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{
string a,b;cin>>a>>b;
a=" "+a;b=" "+b;
for(int i=1;i<a.size();i++)
{
for(int j=1;j<b.size();j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
}
cout<<dp[a.size()-1][b.size()-1];
}8.jmu-ds-最长公共子串
给出2个字符串，输出2字符串的最长公共子串。
输入格式:
输入2个字符串，不可包含空格。
输出格式:
输出2个字符串的最长公共子串。若没有公共子串，则输出“NULL”
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{
string a,b;cin>>a>>b;
a=" "+a;b=" "+b;
int len=0,end;
for(int i=1;i<a.size();i++)
{
for(int j=1;j<b.size();j++)
{
if(a[i]==b[j])
{
dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>len)
len=dp[i][j],end=i;
}
}
}
if(len)
{
for(int i=end-len+1;i<=end;i++)cout<<a[i];
}
else cout<<"NULL";
}9.石子合并
在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。
输入格式:
数据的第 1 行是正整数 N ，表示有 N 堆石子。
第 2 行有 N 个整数，第 i 个整数 ai 表示第 i 堆石子的个数。文章来源：https://www.toymoban.com/news/detail-771683.html
输出格式:
输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。文章来源地址https://www.toymoban.com/news/detail-771683.html
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp1[N][N],dp2[N][N],a[N],s[N];
int main()
{
int n;cin>>n;
memset(dp1,0x3f,sizeof dp1);
memset(dp2,-1,sizeof dp2);
for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
n=2*n-1;
for(int i=1;i<=n;i++)
{
dp1[i][i]=dp2[i][i]=0;
s[i]=s[i-1]+a[i];
}
for(int len=2;len<=n;len++)
for(int l=1;l<=n-len+1;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
{
dp1[l][r]=min(dp1[l][r],dp1[l][k]+dp1[k+1][r]);
dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]);
}
dp1[l][r]+=s[r]-s[l-1];
dp2[l][r]+=s[r]-s[l-1];
}
n=(n+1)/2;
int mi=0x3f3f3f3f,ma=-1;
for(int i=1;i<=n;i++)
{
mi=min(mi,dp1[i][n+i-1]);
ma=max(ma,dp2[i][n+i-1]);
}
cout<<mi<<endl;
cout<<ma<<endl;
}到了这里，关于PTA 动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
