hdu 1087 Super Jumping! Jumping! Jumping! 最大上升子序列。模板題
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.Bkjia.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的原因，就是因為它簡單明了，把一個很原本復雜的問題，解決的如此完美和簡潔。
