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.Bkjia.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;jsum[i])//滿足遞增且當前的sum[i]小與前面中的sum[j]+當前的數
                    sum[i]=sum[j]+num[i];//sum[i]為最長遞增子序列的和,當前num[i]必選。
            }
            if(ans