DP小小总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了DP小小总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2546字,纯文字阅读大概需要4分钟。
内容图文
![DP小小总结](/upload/InfoBanner/zyjiaocheng/1016/7d062347346d4c46a58229718bface21.jpg)
先贴上题目练习
密码20210401
DP之旅开始了~
A
基础方程:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
这样是考虑[i][j]位置可由哪个位置过来
B
巨巨巨坑!看题容易漏条件:
如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k)其中k>1。
/*
前提dp[i][j]=-inf;定义所有为负值
因为现在考虑是[i][j]可以到哪里,到的位置初始值-inf;
*/
dp[1][1]=a[1][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+1][j]);
dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a[i][j+1]);
for(int k=2;k*j<=m;k++)//每次循环求k倍
{
dp[i][j*k]=max(dp[i][j*k],dp[i][j]+a[i][j*k]);
}
}
}
D 最长上升子序列
//dp[i]=1;最初每个对应1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
F
题意:n行人,身高先增后减,最少挑出去多少人
思路:正反向最大递增序列or貌似正向递增+递减最大值也可
1.a[]正存,b[]逆存,dp1[]正增,dp2[]逆增
n-max(dp1[i]+dp2[i])-1;//-1 中间最高的算了两遍
os:不想贴代码了,把D正反鞭尸就行
G 最少拦截系统
题意:导弹拦截系统:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.
面对导弹,最少搞几套导弹拦截系统。
思路:
int main()
{
int n;
while(cin>>n)
{
memset(a,0,sizeof(a));
memset(dp1,0,sizeof(dp1));
for(int i=1;i<=n;i++)
cin>>a[i];
dp1[1]=a[1];
int num=1;
for(int i=1;i<=n;i++)
{
int j;
for( j=1;j<=i;j++)
{
if(a[i]<=dp1[j])
{
dp1[j]=a[i];
break;
}
}
if(j>i)
dp1[++num]=a[i];
}
cout<<num<<'\n';
}
return 0;
}
H 最大上升子序列和
for(int i=1;i<=n;i++)
{
dp[i]=a[i];
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
dp[i]=max(dp[j]+a[i],dp[i]);
}
}
int maxx=0;
for(int i=1;i<=n;i++)
{
maxx=max(maxx,dp[i]);
}
printf("%d\n",maxx);
I
J 最大连续子序列和
推荐指数:***
题意:给一组数,全小于零输出0,else 求最大连续子序列和,并输出该子序列头尾元素。
我相信聪明的你可以看懂代码
os:我不想写了 等我下周码上
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
int a[10010];
int dp[10010];
int start[10010];
int endd[10010];
int max(int x,int y)
{
if(x>y)return x;
else return y;
}
int main()
{
int n;
while(~scanf("%d", &n)&&n)
{
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
memset(start,0,sizeof(start));
memset(endd,0,sizeof(endd));
int f=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>=0)f=1;
}
if(f==0)
{
printf("0 %d %d\n",a[1],a[n]);
continue;
}
int num1=1;
int num2=1;
dp[0]=-1;
for(int i=1;i<=n;i++)
{
dp[i]=max(a[i],dp[i-1]+a[i]);
if(dp[i-1]+a[i]<a[i])
{
start[num1]=a[i];
endd[num2]=a[i];
}
else
{
start[num1]=start[num1-1];
endd[num2]=a[i];
}
num1++;
num2++;
}
int ff;
int maxx=-1;
for(int i=1;i<=n;i++)
{
if(maxx<dp[i])
{
maxx=dp[i];
ff=i;
}
}
printf("%d %d %d\n",maxx,start[ff],endd[ff]);
}
return 0;
}
K bfs
内容总结
以上是互联网集市为您收集整理的DP小小总结全部内容,希望文章能够帮你解决DP小小总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。