首页 > 代码库 > NYOJ-1070诡异的电梯【Ⅰ】

NYOJ-1070诡异的电梯【Ⅰ】

2024-08-10 02:40:07   219人阅读

这道题是个dp，主要考虑两种情况，刚开始我把状态转移方程写成了dp[i] = min(dp[i-1] + a, dp[i + 1] +b); 后来想想当推到dp[i]的时候，那个dp[i + 1]还没有推出来，所以这种方式推导出来不对，后来又看到dp[i] = min(dp[i-2]的所有情况最小值，dp[i-3]的所有情况值)，其中dp[i]表示前 i 层的最小花费总和， dp[i-2]比较好理解，因为不能连着停，所以最近的那个就是dp[i - 2]， dp[i - 3]意思就是停在dp[i - 2]的下一层的时候，这两种就是所有的情况了，其中dp[i-3]的时候情况稍多谢，主要中间隔了两层

dp[i - 3]时：

1. dp[i-2]和dp[i-1]层都向上或者都向下走

2. dp[i-2]向下走，dp[i-1]层 向上走

3.dp[i-2]向上走，dp[i-1]向上走

取他们当中最小的情况就是答案，代码如下：

 1   2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 int dp[100005]; 7 int flo[100005];//保存各个楼层有多少人需要停  8 int main() 9 {10     int kase = 0;11     int T;12     scanf("%d", &T);13     while (T--)14     {15         memset(dp, 0, sizeof(dp));16         memset(flo, 0, sizeof(flo));17         int n, m, a, b;18         scanf("%d %d %d %d", &n, &m, &a, &b);19         for (int i = 0; i < m; i++)20         {21             int t;22             scanf("%d", &t);23             flo[t]++;24         }25         int minn;26         for (int i = 3; i <= n; i++)27         {28             //dp[i-2]中的情况，中间那一层向下或者向上，取最小 29             minn = min(flo[i - 1] * a, flo[i - 1] * b) + dp[i - 2];30             //dp[i-3]中情况，两个都向上走或者两个都向下走 31             int t1 = min(flo[i - 1] * a + flo[i - 2] * a, flo[i - 1] * b + flo[i - 2] * b);32             //dp[i-3]中的情况，上面的向上走，下面的向下走和下面的向上走，上面的向下走 33             int t2 = min(flo[i - 1] * b + flo[i - 2] * a, flo[i - 1] * a + flo[i - 2] * b);34             //取最小 35             int t3 = min(t1, t2) + dp[i - 3];36             dp[i] = min(minn, t3);37         }38         printf("Case %d: %d\n", ++kase, dp[n]);39     }40     41     return 0;42 }

 

NYOJ-1070诡异的电梯【Ⅰ】


联系
我们