4
HDU1087 Super Jumping! Jumping! Jumping!（DP）
source link: https://arminli.com/hdu1087/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1087 Super Jumping! Jumping! Jumping!（DP）
March 06, 2016
题意：水平线上起点终点间有 n 个数，选择一条路线跳过去，要求所选路径上的数字必须不断增加，求所有路径中最大的和。（起点和终点可分别视为无穷小和无穷大）。
简单的动态规划题，设 dp[i]表示以 i 为结尾（所选的最后一个数字）的最大和，那么可列：dp[i] = max(dp[i], dp[j]+a[i]), 1<=j<=i。需要注意的是 dp 初始化应为 a 数组对应的值。 [cpp] #include<stdio.h> #include #include<string.h> #include using namespace std; int a[1005]; int dp[1005]; int main(){ //freopen(“a.txt”, “r”, stdin); int n; while(~scanf(“%d”, &n) && n){ for(int i = 1; i <= n; i++){ scanf(“%d”, &a[i]); } for(int i = 1; i <= n; i++){ dp[i] = a[i]; for(int j = 1; j <= i; j++){ if(a[i] > a[j]) dp[i] = max(dp[i], dp[j]+a[i]); } } int ans = 0; for(int i = 1; i <= n; i++){ ans = max(ans, dp[i]); } cout << ans << endl; } return 0; } [/cpp]
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK