GitBook

这里写图片描述 这里写图片描述

动态规划题目 也是强行没看题解 硬着头皮写 也算是解决了

这一个思路就是对每个点 把到这个点的能获得的最大价值记录下来 然后只需要找出各个点价值的最大值就好了 ……话说这应该就叫DP吧

想想dp的题目也做了有一些了 基本明白了dp的思想 不过还不熟练 有必要更多练习

#include<stdio.h>
int n;
int a[1020],dp[1020];
int main() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	while(scanf("%d",&n),n) {
		int res=0;
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
			dp[i]=a[i];
			if(dp[i]>res)
				res=dp[i];
		}
		for(int i=1; i<=n; i++) {
			for(int j=1; j<i; j++) {
				if(a[j]<a[i]&&dp[i]<dp[j]+a[i])
					dp[i]=dp[j]+a[i];
				if(dp[i]>res)
					res=dp[i];
			}
		}
		printf("%d\n",res);
	}
	return 0;
}

题目地址:【杭电】[1087]Super Jumping! Jumping! Jumping!