nyist 1070 诡异的电梯【Ⅰ】（比较好的DP）

网友投稿 886 2022-11-10

nyist 1070 诡异的电梯【Ⅰ】（比较好的DP）

nyist 1070 诡异的电梯【Ⅰ】（比较好的DP）

题目地址：  停          不停

4   不停    停

3   停        不停

2  不停      停

1 停         不停

如果在第一层和第四层停最少（例如只有这两层有人），则递推方程就不满足这样的条件

如果在第i层停，则上一次停只能在第i-2和第i-3，这样就可以模拟所有停的情况，虽然有些停是没用的，但是不会影响最终的结果

AC代码：

#include #include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int dp[100010];//dp[i]表示在第i层停int visit[100010];using namespace std;int main(){ int t,cas = 1; int n,m,down,up; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); memset(visit,0,sizeof(visit)); scanf("%d%d%d%d",&n,&m,&down,&up); int max1 = 0; for(int i=0; i max1) max1 = loc; } dp[3] = visit[2] * min(up,down);//这一点要注意，第二层的人可以从一层跑上去，也可以从第三层走下来 for(int i=4; i<=max1; i++) { int a = dp[i-2] + visit[i-1] * min(up,down);//中间一层可以上去，也可以下来，取最小值 int b = dp[i-3] + min(visit[i-2] * down,visit[i-2] * up * 2) + min(visit[i-1] * up,visit[i-1] * down * 2); //中间的2个人都可以上去或者下来，取最小值 dp[i] = min(a,b); } int sum = min(dp[max1],dp[max1-1] + visit[max1] * down); printf("Case %d: %d\n",cas++,sum); //printf("Case %d: %d\n",cas++,dp[max1]); //别人这样也过了，个人认为是错的，因为dp[i]的含义是在第i层停，但是第i层不一定停 //也不会出现最后两层都不会停的情况，那样为什么最后一层不停一次呢 } return 0;}

错误代码（递推式就错了）

#include #include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int dp[100010][2];int visit[100010];using namespace std;int main(){ int t,cas = 1; int n,m,down,up; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); memset(visit,0,sizeof(visit)); scanf("%d%d%d%d",&n,&m,&down,&up); int max1 = 0; for(int i=0; i max1) max1 = loc; } for(int i=2; i<=max1; i++) { dp[i][1] = dp[i-1][0] + visit[i-1] * up; dp[i][0] = dp[i-1][1] + visit[i] * down; } int sum = min(dp[max1][1],dp[max1][0]); printf("Case %d: %d\n",cas++,sum); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：代码
上一篇:详解SpringBoot如何自定义Starter
下一篇:2546 饭卡（01背包，挺好的）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~