弹簧高跷题解---双向DP---DD(XYX)的博客

三 . 弹簧高跷

时间限制: 1 Sec 内存限制: 128 MB

题目描述、输入、输出

-----------

方法

这道题用DP是可以解决的。因为每一次跳跃都与前一次跳跃有关，也就是说，每次要枚举前两次的跳跃落点，然后才能计算出某点到一个落点的最优解。这样一来，就可以定义一个 f [ ] [ ] ，f[ i ][ j ] 表示以 “ 从 i 点跳到 j 点 ” 结束的一整次跳跃过程中，得到的最高分 (注意: 可能是 i < j，也可能是 i > j，当然也有 i = j 的情况)。状态转移方程：

(分数)

先处理 f[ i ][ i ] 的情况，然后正逆序都进行一次三重循环。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

void read(int &x) {

    int f = 1;x = 0;char s = getchar();

    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}

    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}

    x *= f;

}

struct no{

    int x,h;

}a[1005];

bool operator < (no a,no b) {

    return a.x < b.x;

}

bool operator > (no a,no b) {

    return b < a;

}

int n,m,s,o,i,j,k,ans = 0;

int dp[1005][1005];

int main() {

    read(n);

    for(i = 1;i <= n;i ++) {

        read(a[i].x);read(a[i].h);

        ans = max(ans,a[i].h);

    }

    sort(a + 1,a + 1 + n);

    for(i = 1;i <= n;i ++) {

        dp[i][i] = a[i].h;

        for(j = 1;j < i;j ++) {

            dp[j][i] = dp[j][j];

            for(k = j - 1;k > 0 && a[j].x - a[k].x <= a[i].x - a[j].x;k --) {

                dp[j][i] = max(dp[j][i],dp[k][j]);

            }

            dp[j][i] += a[i].h;

            ans = max(ans,dp[j][i]);

        }

    }

    for(i = n;i > 0;i --) {

        for(j = n;j > i;j --) {

            dp[j][i] = dp[j][j];

            for(k = j + 1;k <= n && a[k].x - a[j].x <= a[j].x - a[i].x;k ++) {

                dp[j][i] = max(dp[j][i],dp[k][j]);

            }

            dp[j][i] += a[i].h;

            ans = max(ans,dp[j][i]);

        }

    }

    printf("%d",ans);

    return 0;

}

巴特西

弹簧高跷题解---双向DP---DD(XYX)的博客

三 . 弹簧高跷

题目描述、输入、输出

方法

最新文章

热门文章

巴特西

弹簧高跷题解---双向DP---DD(XYX)​​​​​​​的博客

三 . 弹簧高跷

题目描述、输入、输出

方法

最新文章

热门文章

弹簧高跷题解---双向DP---DD(XYX)的博客