私有云平台 k8s file plugins primefaces constructor linktosql swagger cocos2d html5 Font Awesome ddos压力测试 react视频教程 mac虚拟打印机 js空格符 docker的安全特性有哪些 abaqus是什么软件 matlab中如何定义函数 mysql学习 python基础教程免费 python代码 java案例 java环境安装 java类型 java中的队列 java获取当前ip java中接口的定义 高效能人士的七个习惯pdf 俄罗斯方块c语言代码 苹果滚动截屏 python的用途 福昕阅读器绿色版 微信彩色字 mathcad15 win10有几个版本 python电子书 蜘蛛皮肤 js取余数 操作系统安装 sqlprompt android开发案例
当前位置: 首页 > 学习教程  > 编程语言

Codeforces1443B Saving the City

2021/2/13 17:26:14 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目链接 思路:思维题,对于两端连续1中间的0进行计数,0的个数num0与b的乘积即此时将中间连续0填满所需的消费,如果此时的消费小于直接爆破所需的消费a则采取填0爆破的方式,即答案ansnum0*b,否则直接进行爆…

题目链接

思路:思维题,对于两端连续1中间的0进行计数,0的个数num0与b的乘积即此时将中间连续0填满所需的消费,如果此时的消费小于直接爆破所需的消费a则采取填0爆破的方式,即答案ans+=num0*b,否则直接进行爆破,ans+=a,注意下字符串开头的连续0段是无效的,开始时直接过滤掉,对于第一个连续1段,要先加上,因为上述操作是在已经出现连续1段的情况下进行的,漏了最开始的连续1段,因此要加上去,如果没有第一个连续1段则不加

ac代码 46ms:

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define INF 0x3f3f3f3f

using namespace std;

const int N=1e5+10;
int dp[N];
char s[N];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        cin>>(s+1);
        int len=strlen(s+1);
        int ans=0,num0=0,i=1;
        while(s[i]=='0'&&i<=len)i++;
        if(i<=len)ans+=a;
        for(;i<=len;i++){
           if(s[i]=='0')num0++;
           else if(s[i]=='1'&&(s[i+1]=='0'||i==len)){
               if(num0*b<=a)ans+=num0*b;
               else ans+=a;
               num0=0;
           }
        }
        cout<<ans<<endl;
    }
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_700146.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?