Description
给定 \(n\) 个点的位置 \(a_i\) 和每秒的花费 \(b_i\),你的初始位置是 \(s\),你删掉一个点的时间为 \(0\) 秒,走 \(1\) 个单位长度的时间是 \(1\) 秒。请你确定一种关灯顺序,使得所有点的最终花费最小(删掉点后这个点不会再花费)。
Solution
每删掉一个点,有两种选择:继续往前或者往回走,显然是区间型问题。考虑 \(\rm DP\)。设 \(dp[i][j][0/1]\) 表示 \([i,j]\) 区间的点全删掉,现在在 \(i\) 或 \(j\) 的最小花费,设 \(sum_i=\sum\limits_{j=1}^{i} a_j\),易得状态转移方程:
\[dp[i][j][0] = \max\{ dp[i + 1][j][0] + (a_{i+1}-a_i) \times (sum_n-sum_j+sum_i), dp[i+1][j][1]+(a_j-a_i) \times (sum_n-sum_j+sum_i) \} \\ dp[i][j][1] = \max\{ dp[i][j-1][1]+(a_j-a_{j-1}) \times (sum_n-sum_{j-1}+sum_{i-1}), dp[i][j-1][0]+(a_j-a_i) \times (sum_n-sum_{j-1} + sum_{i-1}) \} \]本题难点在于状态表示,转移方程很简单。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 60;
int n, s;
int a[N], b[N], sum[N];
int dp[N][N][2];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
memset(dp, 0x3F, sizeof(dp));
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
sum[i] = sum[i - 1] + b[i];
}
dp[s][s][0] = 0;
dp[s][s][1] = 0;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j][0] = min(dp[i + 1][j][0] + (a[i + 1] - a[i]) * (sum[n] - sum[j] + sum[i]), dp[i + 1][j][1] + (a[j] - a[i]) * (sum[n] - sum[j] + sum[i]));
dp[i][j][1] = min(dp[i][j - 1][1] + (a[j] - a[j - 1]) * (sum[n] - sum[j - 1] + sum[i - 1]), dp[i][j - 1][0] + (a[j] - a[i]) * (sum[n] - sum[j - 1] + sum[i - 1]));
}
}
cout << min(dp[1][n][0], dp[1][n][1]) << "\n";
return 0;
}
标签:路灯,int,题解,sum,删掉,times,花费,P1220,dp
From: https://www.cnblogs.com/unino/p/p1220lg-sol.html