题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1087
分析：简单dp；dp[i] = max (dp[i], dp[j] + a[i])
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<string> 6 #include<cstring> 7 #include<algorithm> 8 #include<functional> 9 #include<iomanip> 10 #include<numeric> 11 #include<cmath> 12 #include<queue> 13 #include<vector> 14 #include<set> 15 #include<cctype> 16 #define PI acos(-1.0) 17 const int INF = 0x3f3f3f3f; 18 const int NINF = -INF - 1; 19 const int maxn = (1 << 15) + 10; 20 typedef long long ll; 21 using namespace std; 22 int n; 23 int arr[1005]; 24 int dp[1005]; 25 int main() 26 { 27 while (scanf("%d", &n) && n) 28 { 29 for (int i = 0; i < n; ++i) 30 scanf("%d", &arr[i]); 31 for (int i = 0; i < n; ++i) dp[i] = arr[i]; 32 for (int i = 0; i < n; ++i) 33 { 34 for (int j = 0; j < i; ++j) 35 { 36 if (arr[i] > arr[j]) 37 dp[i] = max(dp[i], dp[j] + arr[i]); 38 } 39 } 40 int ans = 0; 41 for (int i = 0; i < n; ++i) 42 ans = max(ans, dp[i]); 43 printf("%d ", ans); 44 } 45 return 0; 46 }