1 条题解

  • 0
    @ 2025-4-9 16:13:11
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 200;
    const int INF = 2147483647 / 2;
    int n;
    int t[MAXN + 5];
    int d[MAXN + 5];
    
    int f[MAXN + 5][MAXN + 5][2];
    void calF()
    {
        for (int len = 1; len <= n; len++)
            for (int l = 1; l + len - 1 <= n; l++)
            {
                int r = l + len - 1;
                if (len == 1)
                {
                    f[l][r][0] = f[l][r][1] = 0;
                    continue;
                }
                f[l][r][0] = f[l][r][1] = INF;
                // l->l+1, cal(l+1~r)
                if (t[l] > f[l + 1][r][0] + (d[l + 1] - d[l]))
                    f[l][r][0] = min(f[l][r][0], f[l + 1][r][0] + (d[l + 1] - d[l]));
                // l->r, cal(l+1,r)
                if (t[l] > f[l + 1][r][1] + (d[r] - d[l]))
                    f[l][r][0] = min(f[l][r][0], f[l + 1][r][1] + (d[r] - d[l]));
                // r->r-1, cal(l,r-1)
                if (t[r] > f[l][r - 1][1] + (d[r] - d[r - 1]))
                    f[l][r][1] = min(f[l][r][1], f[l][r - 1][1] + (d[r] - d[r - 1]));
                // r->l, cal(l,r-1)
                if (t[r] > f[l][r - 1][0] + (d[r] - d[l]))
                    f[l][r][1] = min(f[l][r][1], f[l][r - 1][0] + (d[r] - d[l]));
            }
    }
    void outPlan(int l, int r, int now)
    {
        if (now == 0)
        {
            cout << l << " ";
            if (l == r)
                return;
            // l->l+1, cal(l+1~r)
            if (f[l][r][0] == f[l + 1][r][0] + (d[l + 1] - d[l]))
                outPlan(l + 1, r, 0);
            else if (f[l][r][0] == f[l + 1][r][1] + (d[r] - d[l]))
                outPlan(l + 1, r, 1);
        }
        else
        {
            cout << r << " ";
            if (l == r)
                return;
            if (f[l][r][1] == f[l][r - 1][0] + (d[r] - d[l]))
                outPlan(l, r - 1, 0);
            else if (f[l][r][1] == f[l][r - 1][1] + (d[r] - d[r - 1]))
                outPlan(l, r - 1, 1);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        while (cin >> n)
        {
            for (int i = 1; i <= n; i++)
                cin >> t[i];
            for (int i = 1; i <= n; i++)
                cin >> d[i];
            calF();
            if (f[1][n][0] == INF && f[1][n][1] == INF)
                cout << "Mission Impossible";
            else if (f[1][n][0] != INF)
                outPlan(1, n, 0);
            else if (f[1][n][1] != INF)
                outPlan(1, n, 1);
            cout << "\n";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    13403
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    (无)
    递交数
    48
    已通过
    8
    上传者