dis(a,b)就是兩點之間的距離公式
那么這道題該怎么解呢,.先看數據范圍x,y<=1e4,so,18個點兩點之間距離最大18*1e4*sqrt(2)<2^18,所以如果跳過的點大于18個點,那么顯然一個區間內最多不會跳躍超過17個點
現在我們想知道前i個點跳躍幾次在哪跳躍能夠達到最小花費,不妨設跳躍點數為j屬于[0,17],k表示上一個跳躍點距離i的長度
設dp[i][j]表示前i個點跳躍j次,那么上一個跳躍點為i-k-1,由于消耗了j個跳躍點當中的4個跳躍點,所以狀態轉移方程為dp[i][j]=min(dp[i-k-1][j-k]+dis(i,i-k-1)-power(2,j-k-1)+power(2,j-1))為什么要減掉power(2,j-k-1)呢,因為在計算dp[i-k-1][j-k]的時候我們加上過power(2,j-k-1)
首先我們來定義一些基本的數組和變量
constexpr int N = 1e5 + 5;
struct node {double x, y;
};
double dp[N][17];
int P[17];
node a[N];
//i,j,k
//前i個點,有j個點是被跳過的,上一個彎曲點距離點i長度為k,
//i的取值范圍是[2, n],j的取值范圍是[0,min(i-2,16)],k的取值范圍是[1,i-2]
//i能夠取2是為了計算dp[2][0],j表示的是被跳過的點,那么第一個點和第i個點不能被跳過,而且任意兩個點的最大距離為10^4sqrt(10^4)<2^16
//k取1到i-2是因為i-k-1作為起始跳躍點不能為0,且k為0的話起始跳躍點為i的上一個點,兩個點之間無法跳躍
double dis(int x, int y) {double diss = (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y);diss = std::sqrt(diss);return diss;
}
//dis是用來計算兩點之間的距離的接下來我們輸入數據
int main() {int n;std::cin >> n;for (int i = 1; i <= n; i++)std::cin >> a[i].x >> a[i].y;P[0] = 1;//p是2的次冪for (int i = 1; i <= 16; i++)P[i] = P[i - 1] * 2;//由于要計算min值,所以不妨把數組都初始化成一個很大的值for (int i = 1; i <= n; i++) {for (int j = 0; j <= 16; j++) {dp[i][j] = 1e18;}}return 0;
}接下來完成核心代碼
int main() {int n;std::cin >> n;for (int i = 1; i <= n; i++)std::cin >> a[i].x >> a[i].y;P[0] = 1;for (int i = 1; i <= 16; i++)P[i] = P[i - 1] * 2;for (int i = 1; i <= n; i++) {for (int j = 0; j <= 16; j++) {dp[i][j] = 1e18;}}//為什么要單獨把1拎出來,因為我們之前初始化把dp[1][0]也設成1e18了//什么時候會用到1,0?當j==0,i==2,i-1=1時,在下面dp[i][j] = dp[i - 1][j]中會用到dp[1][0] = 0;for (int i = 2; i <= n; i++) {for (int j = 0; j <= std::min(i - 2, 16); j++) {//跳躍點數相同,那就只能是上一個點 dp[i][j] = dp[i - 1][j] + dis(i, i - 1);for (int k = 1; k <= j && i - k - 1 >= 1; k++) {dp[i][j] = std::min(dp[i][j], dp[i - k - 1][j - k] + dis(i - k - 1, i) - P[j - k - 1] + P[j - 1]);}}}double ans = 1e20;for (int j = 0; j <= 16; j++) {ans = std::min(ans, dp[n][j]);}std::cout << std::fixed << std::setprecision(3) << ans << '\n';return 0;
}分別枚舉i到j的范圍,由于i-1不在狀態轉移方程的范圍內,所以我們要在每一次枚舉k之前特殊計算一次dp[i][j]=dp[i-1][j]+dis(i,i-1);
以上就是這道題的詳細解答,還需勤加練習
)
