1 条题解
-
0
#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
- 上传者