Super Jumping! Jumping! Jumping!

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 6 Accepted Submission(s) : 5

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.

The game can be played by two Z http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciBtb3JlIHRoYW4gdHdvIHBsYXllcnMuIEl0IGNvbnNpc3RzIG9mIGEgY2hlc3Nib2FyZKOoxuXFzKOpYW5kIHNvbWUgY2hlc3NtZW6jqMbl19OjqSwgYW5kIGFsbCBjaGVzc21lbiBhcmUgbWFya2VkIGJ5IGEgcG9zaXRpdmUgaW50ZWdlciBvciChsHN0YXJ0obEgb3IgobBlbmShsS4gVGhlIHBsYXllciBzdGFydHMgZnJvbSBzdGFydC1wb2ludCBhbmQgbXVzdCBqdW1wcyBpbnRvIGVuZC1wb2ludCBmaW5hbGx5LiBJbgogdGhlIGNvdXJzZSBvZiBqdW1waW5nLCB0aGUgcGxheWVyIHdpbGwgdmlzaXQgdGhlIGNoZXNzbWVuIGluIHRoZSBwYXRoLCBidXQgZXZlcnlvbmUgbXVzdCBqdW1wcyBmcm9tIG9uZSBjaGVzc21hbiB0byBhbm90aGVyIGFic29sdXRlbHkgYmlnZ2VyICh5b3UgY2FuIGFzc3VtZSBzdGFydC1wb2ludCBpcyBhIG1pbmltdW0gYW5kIGVuZC1wb2ludCBpcyBhIG1heGltdW0uKS4gQW5kIGFsbCBwbGF5ZXJzIGNhbm5vdCBnbyBiYWNrd2FyZHMuIE9uZSBqdW1waW5nCiBjYW4gZ28gZnJvbSBhIGNoZXNzbWFuIHRvIG5leHQsIGFsc28gY2FuIGdvIGFjcm9zcyBtYW55IGNoZXNzbWVuLCBhbmQgZXZlbiB5b3UgY2FuIHN0cmFpZ2h0bHkgZ2V0IHRvIGVuZC1wb2ludCBmcm9tIHN0YXJ0LXBvaW50LiBPZiBjb3Vyc2UgeW91IGdldCB6ZXJvIHBvaW50IGluIHRoaXMgc2l0dWF0aW9uLiBBIHBsYXllciBpcyBhIHdpbm5lciBpZiBhbmQgb25seSBpZiBoZSBjYW4gZ2V0IGEgYmlnZ2VyIHNjb3JlIGFjY29yZGluZyB0byBoaXMKIGp1bXBpbmcgc29sdXRpb24uIE5vdGUgdGhhdCB5b3VyIHNjb3JlIGNvbWVzIGZyb20gdGhlIHN1bSBvZiB2YWx1ZSBvbiB0aGUgY2hlc3NtZW4gaW4geW91IGp1bXBpbmcgcGF0aC48YnI+CllvdXIgdGFzayBpcyB0byBvdXRwdXQgdGhlIG1heGltdW0gdmFsdWUgYWNjb3JkaW5nIHRvIHRoZSBnaXZlbiBjaGVzc21lbiBsaXN0Ljxicj4KCjxwPiA8L3A+CjxoMz5JbnB1dDwvaDM+CjxwPiA8L3A+CklucHV0IGNvbnRhaW5zIG11bHRpcGxlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIGRlc2NyaWJlZCBpbiBhIGxpbmUgYXMgZm9sbG93Ojxicj4KTiB2YWx1ZV8xIHZhbHVlXzIgoa12YWx1ZV9OIDxicj4KSXQgaXMgZ3VhcmFudGllZCB0aGF0IE4gaXMgbm90IG1vcmUgdGhhbiAxMDAwIGFuZCBhbGwgdmFsdWVfaSBhcmUgaW4gdGhlIHJhbmdlIG9mIDMyLWludC48YnI+CkEgdGVzdCBjYXNlIHN0YXJ0aW5nIHdpdGggMCB0ZXJtaW5hdGVzIHRoZSBpbnB1dCBhbmQgdGhpcyB0ZXN0IGNhc2UgaXMgbm90IHRvIGJlIHByb2Nlc3NlZC48YnI+Cgo8cD4gPC9wPgo8aDM+T3V0cHV0PC9oMz4KPHA+IDwvcD4KRm9yIGVhY2ggY2FzZSwgcHJpbnQgdGhlIG1heGltdW0gYWNjb3JkaW5nIHRvIHJ1bGVzLCBhbmQgb25lIGxpbmUgb25lIGNhc2UuPGJyPgoKPHA+IDwvcD4KPGgzPlNhbXBsZSBJbnB1dDwvaDM+CjxwPiA8L3A+Cgo8cHJlIGNsYXNzPQ=="brush:java;">3 1 3 2 4 1 2 3 4 4 3 3 2 1 0

Sample Output

4
10
3

Author

lcy

解题思路：

类似最长递增子序列的想法，只不过这里求的是到第i个元素时，最长递增子序列，各个元素的和。求最大的那个值。

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn=1002; int num[maxn]; int sum[maxn]; int n; int main() { while(scanf("%d",&n)!=EOF&&n) { for(int i=1;i<=n;i++) scanf("%d",&num[i]); sum[1]=num[1]; int ans=sum[1]; for(int i=2;i<=n;i++) { sum[i]=num[i]; for(int j=1;j
     
      sum[i])//满足递增且当前的sum[i]小与前面中的sum[j]+当前的数 sum[i]=sum[j]+num[i];//sum[i]为最长递增子序列的和,当前num[i]必选。 } if(ans

[ACM] hdu 1087 Super Jumping! Jumping! Jumping! （动态规划）