-
题目描述
- 新的宿舍楼有 N(1≤N≤100000) 层 and M(1≤M≤100000)个学生. 在新的宿舍楼里, 为了节约学生的时间也为了鼓励学生锻炼身体, 所以规定该宿舍楼里的电梯在相邻的两层之间是不会连续停下（即，如果在第2层停下就不能在第3层停下。）.所以，如果有学生在相邻的两层之间要停下, 则其中的一部分学生必须选择走楼梯来代替。规定：一个人走下一层楼梯的花费为A，走上一层楼梯的花费为B。（1≤A,B≤100）现在请你设计一个算法来计算出所有学生走楼梯花费的最小费用总和。所有的学生一开始都在第一层，电梯不能往下走，在第二层的时候电梯可以停止。 输入
-
输入有几组数据T。T(1≤T≤10)
每组数据有N (1≤N≤100000),M(1≤M≤100000),A,B(1≤A,B≤100)。
接下来有M个数字表示每个学生想要停的楼层。
输出
- 输出看样例。 样例输入
-
1 3 2 1 1 2 3
样例输出
-
Case 1: 1
题目思路
-
题目要求出所有学生走楼梯花费的时间总和最小是多少，那么我们直接规定dp[ i ] 为电梯停在 i 层时，目前的花费时间最少是多少。在 i 层停止的最少花费受到上一次停止楼层的影响，上一次可以停的位置最近是 i -2 层，因为相邻楼层不能都停止，但在 i - 3 层的时候也能停止， i - 4 ，i - 5 ...都可以停。这样的话情况就很多种。状态转移方程就很难写出，但是其实我们只需要考虑i - 2 层和 i - 3 层即可，i - 4 可以是i - 2停的情况下继续i - 2 停，情况可以覆盖，i - 5可以由 i - 2 后 i - 3 或者i - 3后 i - 2。
-
证明过程：
-
想要证明 i - 2 层停止 和 i - 3层停止就能覆盖所有的情况， 那么我们就需要证明 4 - N的所有数都能用若干个2 和 3组成，即2x + 3y = c。根据扩展欧几里德算法，我们可以求出 2x + 3y = gcd(2, 3)的通解，因为2和3互质，而且该方程的最小正整数解在c > 2*3-2-3 即 c > 1 时获得，所以c为任意值时，x和y都有正整数解。
-
状态转移方程：
-
i 和 i - 2 层停止，那么 i - 1层要下的人可以从 i 层下来，或者i - 2层上去
-
i 和 i - 3 层停止，i - 1 层和 i - 2层要下的人可以从i 层下来，或者从i - 3层上来， 或者一个上一个下（一上一下有2种量情况）。
-
min(v[i-1]*a, v[i-1]*b) + dp[i-2];
-
min(v[i-1]*a+2*v[i-2]*a, 2*v[i-1]*b+v[i-2]*b) + dp[i-3];
min(v[i-1]*b+v[i-2]*a, 2*v[i-1]*a+2*v[i-2]*b) + dp[i-3];
-
题目代码
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define INF 100002
using namespace std;
/*
动态规划
*/
int v[100005];
int dp[100005];
int t, n, m, a, b;
int main(){scanf("%d",&t);int cnt = 0;while(t--){memset(dp, 0, sizeof(dp));memset(v, 0, sizeof(v));scanf("%d%d%d%d",&n,&m,&a,&b);int temp;for(int i = 0; i < m; i++){scanf("%d",&temp);v[temp]++;}for(int i = 3; i <= n; i++){int min1 = min(v[i-1]*a, v[i-1]*b) + dp[i-2];int min2 = min(v[i-1]*a+2*v[i-2]*a, 2*v[i-1]*b+v[i-2]*b) + dp[i-3];min1 = min(min1,min2);int min3 = min(v[i-1]*b+v[i-2]*a, 2*v[i-1]*a+2*v[i-2]*b) + dp[i-3];dp[i] = min(min1, min3);}printf("Case %d: %d\n",++cnt,dp[n]); } return 0;
}