华为鸿蒙 ClickHouse element 网络服务器 java 线程池 DHCP list macos Skeljs GMU Font Awesome vue自定义组件 sql视频教程 jquery的点击事件 js的点击事件 jquery去空格 centos查看php版本 linux源码在线阅读 bootstrap时间轴 hbase集群搭建 kafka消费不到数据 excel带格式复制粘贴 后台管理网站模板 python数据 python类与对象 如何配置python环境 python字符串匹配 java文件 java编程入门 java8函数式接口 java获取本机ip php语言入门 python 教程 圣剑世界 redis入门指南 数据挖掘原理与算法 特战英雄辅助 adobe卸载工具 淘宝图片下载 dos系统下载
当前位置: 首页 > 学习教程  > 编程语言

Codeforces225 C.Barcode(dp)

2020/12/5 10:26:19 文章标签:

题意&#xff1a; 解法&#xff1a; d[i][0/1]表示前i列合法,第i列为颜色k0/1的方案数, 在[x,y]范围内枚举j,设当前为d[i][k], 那么d[ij][k^1]min(d[ij][k^1],d[i][k]([i1,j]颜色变成(k^1)的代价));code&#xff1a; #include <bits/stdc.h> using namespace std; #def…

题意:

在这里插入图片描述

解法:

d[i][0/1]表示前i列合法,第i列为颜色k=0/1的方案数,[x,y]范围内枚举j,设当前为d[i][k],
那么d[i+j][k^1]=min(d[i+j][k^1],d[i][k]+([i+1,j]颜色变成(k^1)的代价));

code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=2e3+5;
char s[maxm][maxm];
int sum[maxm][2];
int a[maxm][2];
int d[maxm][2];
int n,m,x,y;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++){
        cin>>(s[i]+1);
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#'){
                a[j][0]++;
            }else{
                a[j][1]++;
            }
        }
    }
    for(int i=1;i<=m;i++){
        sum[i][0]=sum[i-1][0]+a[i][0];
        sum[i][1]=sum[i-1][1]+a[i][1];
    }
    for(int i=1;i<=m;i++)d[i][0]=d[i][1]=1e18;
    d[0][0]=d[0][1]=0;
    for(int i=0;i<=m;i++){
        for(int k=0;k<2;k++){
            if(d[i][k]==1e18)continue;
            for(int j=x;j<=y&&i+j<=m;j++){
                d[i+j][k^1]=min(d[i+j][k^1],d[i][k]+sum[i+j][k^1]-sum[i][k^1]);
            }
        }
    }
    cout<<min(d[m][0],d[m][1])<<endl;
    return 0;
}


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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?