暑期dp46道(31)--HDOJ 1087 最大上升子序列和 dp(水)

题目链接：HDOJ 1087

裸题，直接上代码：

#include<cstdio> #include<queue> #include<cstring> #include<string> #include<stack> using namespace std; #define M(a) memset(a,0,sizeof(a)) #define Max(a,b) ((a>b)?a:b) #define Min(a,b) ((a<b)?a:b) #define debug 0 const int maxn = 1000 + 5; int dp[maxn], data[maxn]; int n; void Do() { int ans = 0; for (int i = 1; i <= n; i++) { dp[i] = data[i]; for (int j = i - 1; j >= 1; j--) { if (data[j]<data[i] && dp[j] + data[i]>dp[i]) { dp[i] = dp[j] + data[i]; } } ans = Max(ans, dp[i]); // printf("i:%d,dp[i]:%d\n",i,dp[i]); } printf("%d\n", ans); } int main() { #if debug freopen("in.txt", "r", stdin); #endif//debug while (~scanf("%d", &n)) { if (n == 0) break; M(dp); for (int i = 1; i <= n; i++) { scanf("%d", &data[i]); } Do(); } return 0; }