动态规划习题 (R1000-R2300)

状态压缩动态规划

ABC180E: Traveling Salesman among Aerial Cities

R1200

题意

有 \(N \le 17\) 个城市的坐标是 \((X_i,Y_i,Z_i)\) , 从坐标 \((a,b,c)\) 到 \((p,q,r)\) 的距离是 \(|p-a|+|q-b|+\text{max}(0,r-c)\) , 求从 \(1\) 号城市出发，访问完所有城市回到 \(1\) 的最小距离

分析

数据量提示较为明显，考虑状压dp. 用一个Bitmask \(S\) 记录访问过的城市。因为从 \(1\) 号城市出发，还要回到 \(1\) 号城市。可以不妨设开始的时候，\(1\) 号城市没有访问，然后访问完一圈之后回到 \(1\) 正好访问完所有的城市. 设 \(f[S][i]\) 是你访问完 \(S\) 集合中的所有城市，现在的位置在 \(i\) ,那么可以写出下面的方程： \[ f[S][i] = \infin \ ,\ f[0][1] = 0\\ f[S][i]= min(f[S][i], f[S \setminus i][j] + |x_i-x_j| + |y_i-y_j| + \text{max}(0, z_i - z_j)), j \ne i \and (j \in S \or j=1) \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 17 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}


int n, m;
ll x[maxn], y[maxn], z[maxn], f[(1<<(17))+1][18];

int deli(int mask, int i) {
    return mask & (~(1<<(i-1)));
}
int hasi(int mask, int i) {
    return mask & (1<<(i-1));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][1] = 0; 
    for (int mask = 1; mask <= (1<<n)-1; ++mask) {
        for (int i = 1;i <= n; ++i) {
            for (int j = 1;j <= n; ++j) if ((j == 1 || hasi(mask, j)) && j != i) {
                f[mask][i] = min(f[mask][i], f[deli(mask, i)][j] + abs(x[i]-x[j])+abs(y[i]-y[j])+max((ll)0, z[i] - z[j]));
            }
        }
    }
    cout << f[(1<<n)-1][1] << endl;
    return 0;
}

505

分部须抽根烟

最长上升子序列

1427C The Hard Work of Paparazzi

题意

有一个\(r*r (r \le 300)\) 的方格地图，你在开始\(t=0\) 时刻在 \((1,1)\)位置。你知道在 \(t_i\) 时刻会有路人在 \((x_i,y_i)\) 坐标。你从 \((x_1,y_1)\) 走到 \((x_2,y_2)\) 需要花费 \(|x_1-x_2|+|y_1-y_2|\) 的时间。一共有 \(n \le 10^5\) 个路人，你想给路人拍照，拍照不花费时间。在每个时刻你可以等待或走到其他位置。你知道所有路人的时间 \(t_i < t_{i+1}\) 。求你最多可以给多少个路人拍照。

分析

如果你可以从一个路人 \(j\) 的位置走到另一个路人 \(i\) 的位置。所花费的时间 \(|x_i-x_j|+|y_i-y_j|\) 正好不大于两个路人出现时间的差 \(t_i-t_j\)。设 \(f(i)\) 是以第 \(i\) 个路人结束的最大答案。那么 \(f(i) = max\{f(i), f(j) + 1\}\) . 这个就是基本的状态转移方程。由于地图比较小，所以花费时间最多是 \(2r\) ，而路人的时间是严格单调递增的。那么也就是说，当 \(j < i-2r\) 的时候，\(j\) 就一定可以走到 \(i\) 。所以我们只要枚举之前 \(2r\) 个路人即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}
const int maxm = 300 + 5;

int n, m, r, f[maxn], t[maxn], x[maxn], y[maxn], ind[maxm][maxm], mx[maxn], ans;

bool cango(int i, int j) {
    return t[j] - t[i] >= abs(x[i] - x[j]) +  abs(y[i] - y[j]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> n;
    x[0] = 1; y[0] = 1; fill(f+1,f+n+1, INT_MIN/2); f[0] = 0; fill(mx+1, mx+n+1, INT_MIN/2);
    for (int i = 1;i <= n; ++i) {
        cin >> t[i] >> x[i] >> y[i];
        for (int j = max(0, i - 2*r); j < i; ++j) {
            if (cango(j, i)) f[i] = max(f[i], f[j] + 1);
        }
        if (i - 2*r >= 0) f[i] = max(f[i], mx[i - 2*r] + 1);
        mx[i] = max(mx[i-1], f[i]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}