HDU 1087 Super Jumping! Jumping! Jumping!
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1087 题目翻译 数字小的点可以跳往数字大的点，求最大收集数字和。 题解 暴力DP，不赘述 代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<cstdio> #include<algorithm> #include<cstring> #define LL long long using namespace std; const int Maxn = 1000; int n; LL num[Maxn + 5], DP[Maxn + 5]; inline void solve() { for (int i = 1; i <= n; i++) scanf("%lld", &num[i]); memset(DP, 0, sizeof(DP)); for (int i = 1; i <= n; i++){ DP[i] = num[i]; for (int j = 1; j < i; j++){ if (num[i] > num[j] && DP[i] < DP[j] + num[i]){ DP[i] = DP[j] + num[i]; } } } LL Ans = 0; for (int i = 1; i <= n; i++) Ans = max(Ans, DP[i]); printf("%lld\n", Ans); } int main() { while(scanf("%d", &n) != EOF) if (n != 0) solve(); else return 0; return 0; } |
