Super Jumping! Jumping! Jumping!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24374 Accepted Submission(s): 10740
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+CllvdXIgdGFzayBpcyB0byBvdXRwdXQgdGhlIG1heGltdW0gdmFsdWUgYWNjb3JkaW5nIHRvIHRoZSBnaXZlbiBjaGVzc21lbiBsaXN0Ljxicj4KCiAKPGJyPgpJbnB1dApJbnB1dCBjb250YWlucyBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBkZXNjcmliZWQgaW4gYSBsaW5lIGFzIGZvbGxvdzo8YnI+Ck4gdmFsdWVfMSB2YWx1ZV8yIKGtdmFsdWVfTiA8YnI+Ckl0IGlzIGd1YXJhbnRpZWQgdGhhdCBOIGlzIG5vdCBtb3JlIHRoYW4gMTAwMCBhbmQgYWxsIHZhbHVlX2kgYXJlIGluIHRoZSByYW5nZSBvZiAzMi1pbnQuPGJyPgpBIHRlc3QgY2FzZSBzdGFydGluZyB3aXRoIDAgdGVybWluYXRlcyB0aGUgaW5wdXQgYW5kIHRoaXMgdGVzdCBjYXNlIGlzIG5vdCB0byBiZSBwcm9jZXNzZWQuPGJyPgoKIAo8YnI+Ck91dHB1dApGb3IgZWFjaCBjYXNlLCBwcmludCB0aGUgbWF4aW11bSBhY2NvcmRpbmcgdG8gcnVsZXMsIGFuZCBvbmUgbGluZSBvbmUgY2FzZS48YnI+CgogCjxicj4KU2FtcGxlIElucHV0Cgo8cHJlIGNsYXNzPQ=="brush:java;">3 1 3 2 4 1 2 3 4 4 3 3 2 1 0
Sample Output
4
10
3
先写上状态转移公式：dp[i]=max{dp[j]+num[i]}(num[i]>num[j],j
#include
#define INF 100000000 #define MAX 1010 int max(int a , int b) { return a>b?a:b ; } int main() { int dp[MAX],num[MAX] , n; while(~scanf("%d",&n) && n) { for(int i = 1 ; i <= n ; ++i) { scanf("%d",&num[i]) ; dp[i] = 0 ; } dp[0] = 0 ; int ans = -INF ; for(int i = 1 ; i <= n ; ++i) { dp[i]=num[i]; for(int j = 1 ; j <= i ; ++j) { if(num[j]
我喜欢DP的原因，就是因为它简单明了，把一个很原本复杂的问题，解决的如此完美和简洁。