h2>题目描述

游戏在一行N个方块中进行，编号为1到N，一开始Alice在方块1中，第一次只能跳到方块2中，接下来每一次跳跃必须满足以下两个限制： 
　　（1） 如果是向前跳（即跳到比现在编号大的方块），跳跃距离必须比上一次要大1； 
　　（2） 如果是向后跳（即跳到比现在编号小的方块），跳跃距离必须跟上一次一样。 
　　例如，第一次跳跃后，Alice可以跳回1也可以跳到4。 
　　每进入一个方块，Alice必须支付一定的费用，Alice的目标花最少的钱从方块1跳到方块N。编程计算最小的花费。

思路

我们设f[i][j]表示走到底i个点，上一步走了j要用的最少步数

转移显然

但是我们考虑到当前的j可能会影响到前面的j，所以我们在暴力跑出当前的可以往后跳的点在顺着跑一下就可以解决这个问题，然后因为我们每一个都会往前一直跳，所以我们在跳到一个跳过的点时就可以退出了

#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define N 1001
#define INF 0x7f7f7f7f
#define min(x, y) ((x) < (y) ? (x) : (y))
int a[N], f[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    fill(f, INF);
    f[0][0] = 0;
    f[1][0] = 0;
    int tot = 0;
    for (int j = 0; j <= n; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (i + j + 1 <= n) f[i + j + 1][j + 1] = min(f[i + j + 1][j + 1], f[i][j] + a[i + j + 1]);
            int t = i;
            bool fl = 1;
            while (t - j >= 1 && j != 0 && fl) 
            {
                fl = 0;
                if (f[t - j][j] > f[t][j] + a[t - j])
                {
                    f[t - j][j] = f[t][j] + a[t - j];
                    fl = 1;
                }
                t -= j;
            }
        } 
        for (int i = 1; i <= n; i++)
            if (i + j + 1 <= n) f[i + j + 1][j + 1] = min(f[i + j + 1][j + 1], f[i][j] + a[i + j + 1]);
    }
    int ans = INF;
    for (int i = 0; i <= n; i++)
        ans = min(ans, f[n][i]);
    printf("%d\n", ans);
    return 0;
}