首页 > 代码库 > dp 动态规划 hdu 1003 1087
dp 动态规划 hdu 1003 1087
动态规划就是寻找最优解的过程
最重要的是找到关系式
hdu 1003
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003
题目大意：求最大字序列和,其实就是分成
以0结尾的序列
以1结尾的序列
以2结尾的序列
...
以n结尾的序列
所以以n结尾的序列的最大值就是以n－1结尾的序列的最大值＋n的值
或最大值是n的值
关系式： d[i]=max（d[i-1]+a[i],a[i]） d[i]为以i结尾的序列和的最大值，a[i]为第i个数的值
#include<iostream>#include<cmath>#include<algorithm>using namespace std;long long a[100000];long long d[100000];int t[1000];int main(){ int T,k=1,mi; long long maxi=-1000,m=0; cin>>T; while(T--) { int flag=1; int x=0; maxi=-1000; m=0; int n,p; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } d[0]=0; for(int i=1;i<=n;i++) { if(d[i-1]+a[i]>=a[i]) d[i]=d[i-1]+a[i]; else d[i]=a[i]; } for(int i=1;i<=n;i++) { if(d[i]>maxi) { maxi=d[i]; p=i; } } for(int j=p;j!=0;j--) { m=m+a[j]; if(m==maxi) { t[x]=j; } } sort(t,t+x); mi=t[0]; while(a[mi-1]==0&&mi!=1) { mi--; if(mi==1) break; } cout<<"Case "<<k++<<":"<<endl; cout<<maxi<<" "<<mi<<" "<<p<<endl; if(T!=0) cout<<endl; } return 0;}
hdu 1087
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1087
题目大意：找出最大字序列和，其中字序列不一定是相邻的数，但需满足v[i]<v[j] 其中i<j
题解： 与上题一样，都是以d[n]结尾的字序列，不同的是它不能只根据d[n-1]就得到，需要从0～n-1的d［］值依次与d［n］判断，求最大值
关系式：d[i]=max{d[j]+v[i],v[i]}
#include<iostream>using namespace std;int v[1005];int d[1005];int main(){ int n,i,j,max; while(cin>>n) { if(n==0) break; for(i=0;i<n;i++) cin>>v[i]; max=v[0]; d[0]=v[0]; for(i=1;i<n;i++) { d[i]=v[i]; for(j=0;j<i;j++) { if(v[i]>v[j]) { if(d[i]<d[j]+v[i]) d[i]=d[j]+v[i]; } } if(d[i]>max) //注意一直更新最大值 max=d[i]; } cout<<max<<endl; } return 0;}
dp 动态规划 hdu 1003 1087
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。