D. Cakes for Clones
You live on a number line. You are initially (at time moment 𝑡=0) located at point 𝑥=0. There are 𝑛 events of the following type: at time 𝑡𝑖 a small cake appears at coordinate 𝑥𝑖. To collect this cake, you have to be at this coordinate at this point, otherwise the cake spoils immediately. No two cakes appear at the same time and no two cakes appear at the same coordinate.
You can move with the speed of 1 length unit per one time unit. Also, at any moment you can create a clone of yourself at the same point where you are located. The clone can't move, but it will collect the cakes appearing at this position for you. The clone disappears when you create another clone. If the new clone is created at time moment 𝑡, the old clone can collect the cakes that appear before or at the time moment 𝑡, and the new clone can collect the cakes that appear at or after time moment 𝑡.
Can you collect all the cakes (by yourself or with the help of clones)?
Input
The first line contains a single integer 𝑛 (1≤𝑛≤5000) — the number of cakes.
Each of the next 𝑛 lines contains two integers 𝑡𝑖 and 𝑥𝑖 (1≤𝑡𝑖≤109, −109≤𝑥𝑖≤109) — the time and coordinate of a cake's appearance.
All times are distinct and are given in increasing order, all the coordinates are distinct.
Output
Print "YES" if you can collect all cakes, otherwise print "NO".
Examples
input
3
2 2
5 5
6 1
output
YES
1 0
6 2
2 1
6 0
NO
Note
In the first example you should start moving towards 5 right away, leaving a clone at position 1 at time moment 1, and collecting the cake at position 2 at time moment 2. At time moment 5 you are at the position 5 and collect a cake there, your clone collects the last cake at time moment 6.
In the second example you have to leave a clone at position 0 and start moving towards position 5. At time moment 1 the clone collects a cake. At time moment 2 you should create a new clone at the current position 2, it will collect the last cake in future. You will collect the second cake at position 5.
In the third example there is no way to collect all cakes.
翻譯
有一條線，你站在0這個點。
現在有n個事件，表示有一個蛋糕将會在t[i]秒出現在x[i]的位置，你每秒可以移動1，然後你的任務是吃掉所有的蛋糕。
你現在有個功能，就是你可以在你的位置生成一個克隆，這個克隆不能移動，可以一直呆在原地吃蛋糕，但是同時隻能存在一個蛋糕。
問你是否存在一個方案吃掉所有的蛋糕。
題解
考慮最最暴力的dp, dp[i][j]表示吃掉1~i，克隆體在第j個位置的最小花費是多少。
3方的dp
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
for (int k=i-1;k<=n;k++) {
if (j!=k) {
dp[i][j]=min(dp[i][j], cost + dp[i-1][k]);
}
}
// 轉移一下 j==k 的情況，就可以到處放克隆體
}
}
n3肯定是會TLE的，優化一下發現有些狀态是不需要的，我們不需要存儲克隆體在j的最小花費。
我們定義minTime[i]，表示我們在吃完了[1,i-1]所有蛋糕，且我在x[i]的最小花費是多少
dp[i][j]表示吃完了[1,i]的所有蛋糕，人在x[i]，分身放在x[j]是否可行。
代碼
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int n;
long long t[maxn],x[maxn];
long long dp[maxn][maxn],minTime[maxn];
long long dis(long long x,long long y) {
return abs(x-y);
}
int main() {
cin>>n;
for (int i=1;i<=n;i++) {
cin>>t[i]>>x[i];
minTime[i] = 1e17;
}
minTime[0]=0;
dp[0][0]=1;
for (int i=1;i<=n;i++) {
if (x[i] == 0) {
dp[0][i]=1;
}
}
for (int i=1;i<=n;i++) {
// 從x[i-1]點出發, 不靠分身
if (minTime[i-1] <= t[i-1]) {
minTime[i] = min(minTime[i], max(minTime[i-1] + dis(x[i], x[i-1]), t[i-1]));
if (minTime[i] <= t[i]) {
dp[i][i]=1;
}
}
// 站在i點，分身放在j點，又回來
for (int j=i;j<=n;j++) {
if (minTime[i]+2*dis(x[i],x[j])<=t[i]) { // 過去又回來
dp[i][j]=1;
}
}
// 從i-1點出發，人在i，分身仍然留在j
for (int j=i+1;j<=n;j++) {
if (dp[i-1][j] && t[i-1] + dis(x[i], x[i-1]) <= t[i]) {
dp[i][j] = 1;
}
}
// 從i-1 -> j放下分身，i-1 -> i吃
for (int j=i+1;j<=n;j++) {
if (minTime[i-1]<=t[i-1] && max(t[i-1],minTime[i-1]+dis(x[j],x[i-1]))+dis(x[j],x[i])<=t[i]) {
dp[i][j]=1;
}
}
// 2 dp[i-1][i]是合法的 -> dp[i+1][i] / minTime[i+1]
if (dp[i-1][i] && i+1 <= n) {
minTime[i+1] = min(minTime[i+1], max(t[i-1] + dis(x[i+1],x[i-1]), t[i]));
if (minTime[i+1] <= t[i+1]) {
dp[i+1][i+1]=1;
}
// 先去j，等待分身i吃完，放下分身，再去i+1
for (int j=i+1;j<=n;j++) {
if (max(t[i-1]+dis(x[j],x[i-1]),t[i])+dis(x[j],x[i+1]) <= t[i+1]) {
dp[i+1][j] = 1;
}
}
}
}
if (dp[n][n] == 1 || dp[n-1][n] == 1) {
cout<<"YES"<<endl;
} else {
cout<<"NO"<<endl;
}
}