我尝试用dp来做这道题,但是写到相遇的代码时,就卡住了,不会写了。有没有哪位大佬愿意辅导一下我这只小菜鸡
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
int a[1100];
int dp[2200], dp1[2200];
int main(){
int l, n;
cin >> l >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
dp[i] = a[i];
dp1[i] = a[i];
}
for(int i = 1; i <= n; i++){//有两种情况,分辨是向左或右走,寻找时间最少方向。
dp[i] = min(dp[i], min(a[i]--, l - (a[i]++)));
}
for(int i = 1; i <= n; i++){
dp1[i] = max(dp1[i], max(a[i]--, l - (a[i]++)));//作死,走哪个方向耗得时间越长往哪走。
}
cout << dp[n] << endl << dp1[n];
return 0;
}