Super Jumping! Jumping! Jumping!
搬中文ing
Descriptions:
wsw成功的在zzq的幫助下獲得了與小姐姐約會的機會，同時也不用擔心wls會發現了，可是如何選擇和哪些小姐姐約會呢？wsw希望自己可以循序漸進，同時希望挑戰自己的極限，我們假定每個小姐姐有一個“攻略難度值” 從攻略成功第一個小姐姐開始，wsw希望每下一個需要攻略的小姐姐難度更高，同時又希望攻略難度值之和最大，好了，現在小姐姐們排成一排，wsw只能從左往右開始攻略，請你幫助他找到最大的攻略難度和
Input
多組輸入，每組資料占一行，每行一個整數n表示小姐姐個數，接著n個數a_1, a_2, ..., a_n表示第i個的小姐姐攻略難度 (a_i在32位有符號整型范圍內)，n = 0表示輸入結束 (0 <= n <= 1000)，
Output
一個數，最大攻略和
Sample Input
3 1 3 2 4 1 2 3 4 4 3 3 2 1 0
Sample Output
4 10 3
題目鏈接
https://vjudge.net/problem/HDU-1087
求解最大遞增子序列和 不要求是連續的最大遞增子序列，但是一定要注意是遞增的
dp[i]表示的是前i個并且包含第i個的最大遞增子序列和
若a[i]>a[j] dp[i]=dp[j]+a[i]
開兩個for回圈全部遍歷一遍即可
AC代碼
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x, y) memset(x, y, sizeof(x)) #define Maxn 1000+10 using namespace std; int n; int dp[Maxn]; int a[Maxn]; int main() { while(cin>>n&&n!=0) { MEM(dp,0);//初始化 MEM(a,0); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+a[i]); } dp[i]=max(dp[i],a[i]); } sort(dp,dp+n); cout<<dp[n-1]<<endl; } return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205310.html
標籤：其他
下一篇：區間操作---樹狀陣列&&線段樹