USACO 2014 Dec Silver 2.Marathon

2015.03.04 11:21 Wed| 17 visits oi_2015| 2015_刷题日常| Text

Solution

简单 DP。令 f[i][j] 表示走到 i 点,跳过了 j 个点的最小总代价。时间复杂度 $\mathcal O(N * K ^ 2)$,时间 684ms。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 505
#define inf 0x3f3f3f3f

int n, t, x[N], y[N], f[N][N], ans = inf;

int dist(int a, int b)
{
    return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}

int main()
{
    cin >> n >> t;
    for (int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 1; i < n; ++i)
        for (int k = 0; k <= t; ++k)
            for (int j = i + 1; j <= n && k + j-i-1 <= t; ++j)
                f[j][k + j-i-1] = min(f[j][k + j-i-1], f[i][k] + dist(i, j));
    for (int i = 0; i <= t; ++i)
        ans = min(ans, f[n][i]);
    cout << ans << endl;
    return 0;
}