问题描述
问题分析
动态规划题目
也是强行没看题解 硬着头皮写
也算是解决了
这一个思路就是对每个点
把到这个点的能获得的最大价值记录下来
然后只需要找出各个点价值的最大值就好了
……话说这应该就叫DP吧
想想dp的题目也做了有一些了
基本明白了dp的思想
不过还不熟练 有必要更多练习
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #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!