训练第三周之dp习题

个人感觉做dp题目就是求什么就设什么，dp[i]数组就是所求，然后找出子问题，写出状态转移方程就差不多出来了

1、Max Sum-hdu1003

思路：

这个题目思路很简单，就是求子串最大和。但是就是要记录开头结尾还有如果相等记录第一个，让我吃尽了苦头。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],dp[100005];
int rem[100005],s,k;
int main()
{
int t,n,i,Max,j,m;
scanf("%d",&t);
k=1;
do
{
if(k>1)
printf("n");
scanf("%d",&n);
memset(dp,0,sizeof(dp));
s=1;
rem[1]=1;
m=j=1;//j记录最大和子串的开始，m记录结尾
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Max=a[1];
///记录最大值
for(i=1;i<=n;i++)
{
if(dp[i-1]>=0)
{
dp[i]=dp[i-1]+a[i];//前i个元素中连续子串最大和
if(Max==dp[i])//只有该最大值第一次出现记录，以后出现不记录
if(rem[1]==j)
{
m=i;
}
if(Max<dp[i]){
Max=dp[i];
j=rem[1];
m=i;
}
rem[s++]=i;//记录最大和子串
//printf("%d %dn",j,m);
}
else
{
dp[i]=a[i];
s=1;
rem[s++]=i;
if(Max<a[i])
{
Max=a[i];
j=i;
m=i;
}
//printf("%d %dn",s,rem[s-1]);
}
}
/*for(i=0;i<s;i++)
printf("%dn",rem[i]);*/
if(j!=m){
printf("Case %d:n",k);
printf("%d %d %dn",Max,j,m);
}
else//j等于m说明最大值子串只有一个数
{
for(i=1;i<=n;i++)
if(Max==a[i])
break;
printf("Case %d:n",k);
printf("%d %d %dn",Max,i,i);
}
k++;
}while(k<=t);
}

2、Humble Numbers-hdu1058

思路：

这题意思是要求质因数只有2,3,5,7的数的编号。本来我是从1到2000000000，是质因数的就记录，发现爆时间了，后面看题解才知道可以直接求第1个到第5842个质因数。dp[i]指第i项总可以由前i-1项中的某一项与2,3,5,7相乘得到，且为大于第i-1项的最小值。我隐隐觉得，dp[i]就是求什么就设成什么。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
long long f[6000];/*第i项总可以由前i-1项中的某一项与2,3,5,7相乘得到，且为大于第i-1项的最小值*/
int way[4]={2,3,5,7};
int main()
{
int i,j,k,t,n;
memset(f,-1,sizeof(f));
f[1]=1;
for(i=2;i<=5842;i++)
{
for(j=0;j<4;j++)
for(k=i-1;k>=1;k--)
{
if(f[k]*way[j]<=f[i-1])
break;
if(f[k]*way[j]<f[i]||f[i]<0)
f[i]=f[k]*way[j];
}
}
//printf("%dn",f[1000]);
while(scanf("%d",&n)!=EOF&&n)
{
printf("The %d",n);
if(n%10==1&&n%100!=11){printf("st humble number is %d.n",f[n]);continue;}
if(n%10==2&&n%100!=12){printf("nd humble number is %d.n",f[n]);continue;}
if(n%10==3&&n%100!=13){printf("rd humble number is %d.n",f[n]);continue;}
printf("th humble number is %d.n",f[n]);
}
return 0;
}

3、最少拦截系统-hdu1257

思路：

这题我不知道是不是用的dp，就是判断是否有系统目前高度大于敌方导弹高度，如果有就用最相近的那个去拦截，如果没有就再加一台系统

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
int s;
int f[10005];
int main()
{
int n,i,j,flag,m,t,k;
while(scanf("%d",&n)!=EOF)
{
s=0;
memset(f,0,sizeof(f));
for(i=0;i<n;i++)
{
scanf("%d",&m);
flag=0;
k=1;
t=2e9;
for(j=1;j<=s;j++)
{
if(f[j]>=m)
{
flag=1;
if(t>f[j]-m)
{
t=f[j]-m;
k=j;
}
}
}
if(flag)
{
f[k]=m;
}
else
{
f[++s]=m;
}
}
printf("%dn",s);
}
return 0;
}

4、Monkey and Banana-hdu1069

思路：

这题我不用dp能得出结果就是ac不了，我也发现漏洞了，解决不了就只能看题解了。。。题解比较巧妙，将每种积木直接变成三种积木，每种只有一个底面一个高，再排序，就一下简化了很多，再根据状态转移方程，放i个积木就是放前i-1个中底面比第i个底面大的加上第i个的高的最大高度

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct dimensions
{
int x,y,z;
}dim[100];
int dp[100];
int t=0;
typedef struct dimensions d;
bool cmp(d a,d b)
{
if(a.x==b.x)
return a.y>b.y;
return a.x>b.x;
}
int main()
{
int n,i,j,a,b,c,maxdp;
while(cin>>n&&n)
{
j=0;
for(i=0;i<n;i++)//将每种积木变成三种只有一个底面一个高的积木，分别存入dim[j]到dim[j+2]
{
cin>>a>>b>>c;
dim[j].x=min(a,b);
dim[j].y=max(a,b);
dim[j].z=c;
dim[j+1].x=min(a,c);
dim[j+1].y=max(a,c);
dim[j+1].z=b;
dim[j+2].x=min(b,c);
dim[j+2].y=max(b,c);
dim[j+2].z=a;
j+=3;
}
n=j;
sort(dim,dim+n,cmp);//将积木按底面从大到小排序
maxdp=0;
//cout<<n<<endl;
for(i=0;i<n;i++)
{
dp[i]=dim[i].z;
for(j=i-1;j>=0;j--)
{
if(dim[j].x>dim[i].x&&dim[j].y>dim[i].y)
if(dp[j]+dim[i].z>dp[i])
dp[i]=dp[j]+dim[i].z;
}
if(dp[i]>maxdp)//dp[i]为放第i个积木能达到的最大高度
maxdp=dp[i];
}
cout<<"Case "<<++t<<":";
cout<<" maximum height = "<<maxdp<<endl;
}
}

5、Distribute Message-hdu1723

思路：

dp[i]表示从n到i的方法数。所以状态转移方程为 dp[i-j]=dp[i]+dp[i-j];

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[50];//从n到i的次数
int main()
{
int n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
memset(dp,0,sizeof(dp));
dp[n]=1;
for(i=n;i>=1;i--)
{
for(j=1;j<=m;j++)
{
if(i>=j)
dp[i-j]=dp[i]+dp[i-j];
}
}
printf("%dn",dp[1]);
}
return 0;
}

最后

以上就是美丽哈密瓜为你收集整理的训练第三周之dp习题的全部内容，希望文章能够帮你解决训练第三周之dp习题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。