【枚举+DP】Technocup 2021 - Elimination Round 2 C. Bouncing Ball

红太狼 2024-03-22 18:59 2阅读 0赞

[Problem - C - Codeforces][]

题意：

![de0a1baa634d4b9db8eb4740c021f59d.png][]

![b28272a14e3040ea803178ea865b2dc5.png][]

思路：

![0099c657af494008b8c71ddfb523221e.png][]

![d57033bd69cc4b96898606904485da51.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    string s;
    
    int N,p,k,x,y;
    int dp[mxn];
    
    void solve(){
        s.clear();
        cin>>N>>p>>k;
        cin>>s;
        s=" "+s;
        cin>>x>>y;
        for(int i=N;i>=1;i--){
            if(i+k>N){
                if(s[i]=='1') dp[i]=0;
                else dp[i]=x;
            }else{
                if(s[i]=='1') dp[i]=dp[i+k];
                else dp[i]=dp[i+k]+x;
            }
        }
        int ans=2e18;
        for(int i=1;i<=N+1-p;i++){
            ans=min(ans,dp[i+p-1]+(i-1ll)*y);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1415/problem/C
[de0a1baa634d4b9db8eb4740c021f59d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4c05f5b3481c47ad96ad15915ba50267.png
[b28272a14e3040ea803178ea865b2dc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/ac40e35036584745a512bee08927b6c4.png
[0099c657af494008b8c71ddfb523221e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/ca26afc17c104b20a448af6ff140af3e.png
[d57033bd69cc4b96898606904485da51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/2b8d17c7f9374d9b9c517018323ecfe1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关【枚举+DP】Technocup 2021 - Elimination Round 2 C. Bouncing Ball

[Problem - C - Codeforces][] 题意： ![de0a1baa634d4b9db8eb4740c021f59d.png][] ![b28272a1

红太狼/ 2024年03月22日 18:59/ 0 赞/ 3 阅读

相关 C枚举

![1598479-20190917163036384-274404394.png][] 转载于:https://www.cnblogs.com/yunshangyue

Myth丶恋晨/ 2023年08月17日 16:05/ 0 赞/ 144 阅读

相关 c++枚举和c语言枚举_C语言枚举初学者指南

c++枚举和c语言枚举 Hey, folks! Hope you all are doing well. In this article, we will be discus

曾经终败给现在/ 2023年02月28日 06:05/ 0 赞/ 236 阅读

相关 C#——枚举

枚举 ![0_13315183659D8L.gif][] > 声明枚举的条件：确定数量，确定值的取值范围。 > > 枚举的语法：（1）声明枚举的时候和类同级。 > >

灰太狼/ 2022年08月26日 04:48/ 0 赞/ 250 阅读

相关 C++枚举

1. 介绍第一次学习枚举类型时，觉得这个名字很诡异。但是后来发现，“枚举”真的特别传神，枚举就是可数的意思。当你发现某个类型的值是数得过来的，那就派枚举出场吧。

你的名字/ 2022年08月05日 00:58/ 0 赞/ 254 阅读

相关 Technocup 2017 - Elimination Round 2 D. Sea Battle

算是正式开始康复训练啦这是一题简单的思维题… 第一想法是鸽巢原理，因为“最小数量“，“至少一个“等关键词。那么，就要先知道鸽巢的总数，也就是可能是船的位置的数量。

忘是亡心i/ 2022年07月14日 01:00/ 0 赞/ 96 阅读

相关枚举【C#】

简单总结一下枚举的用法：什么是枚举？枚举简单的说是一种数据类型，只不过这种数据类型只包含自定义的特定数据，它是一组有共同特性的数据的集合。举个例子，颜色也可以

一时失言乱红尘/ 2022年06月16日 05:44/ 0 赞/ 257 阅读

相关 C#枚举

Gender.cs 解决方案管理器--->右击项目--->添加/类--->代码文件 /// <summary> /// 性别类型

àì夳堔傛蜴生んèń/ 2022年01月23日 22:57/ 0 赞/ 279 阅读

相关 C#枚举

using System; using System.Collections.Generic; using System.Linq; using System.Text;

秒速五厘米/ 2022年01月10日 15:49/ 0 赞/ 297 阅读

相关 C - Bouncing Ball

C - Bouncing Ball C. Bouncing Ball time limit per test 1 second memory l

小灰灰/ 2021年07月16日 23:28/ 0 赞/ 258 阅读