C. Barcode --待补思路

以你之姓@ 2023-01-22 05:59 1阅读 0赞

[  
https://codeforces.com/contest/225/problem/C][https_codeforces.com_contest_225_problem_C]

#include<iostream>
    #include<cmath>
    #include<cstring>
    #define LL long long
    #define INF 0x3f3f3f3f
     
    using namespace std;
     
    const int maxn=1e3+100;
    char mp[maxn][maxn];
    int a[maxn],b[maxn];
    int dp[maxn][2];
    int main()
    { 
        int n,m,x,y;
        cin>>n>>m>>x>>y;
        for(int i=1;i<=n;i++)
        { 
            cin>>mp[i]+1;
        }
        
        for(int i=1;i<=m;i++)
        { 
            int cnt1=0,cnt2=0;
            for(int j=1;j<=n;j++)
            { 
                if(mp[j][i]=='#')
                { 
                    cnt1++;
                }
                else
                { 
                    cnt2++;
                }
            }
            a[i]=a[i-1]+cnt1; // 一列中 # 的个数
            b[i]=b[i-1]+cnt2; // 一列中 * 的个数
            //cout << a[i] << " " << b[i] <<endl;
        }
        memset(dp,INF,sizeof(dp)); // 初始化
        
        dp[0][0]=dp[0][1]=0; 
        // dp[i][0] 
        // dp[i][1] 
        
        for(int i=0;i<m;i++) // 
        { 
            for(int j=x;j<=y;j++) // 连续列数 x <= j <= y
            { 
                if(i+j<=m)
                { 
                    //cout << i + j << endl;
                    dp[i+j][0]=min(dp[i+j][0], dp[i][1]+a[i+j]-a[i]); //
                    dp[i+j][1]=min(dp[i+j][1], dp[i][0]+b[i+j]-b[i]); //
                }
            }
        }
        int ans=min(dp[m][0],dp[m][1]);
        
        cout<<ans<<endl;
        return 0;
    }

[https_codeforces.com_contest_225_problem_C]: https://codeforces.com/contest/225/problem/C

发表评论取消回复

表情：

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

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

相关阅读

相关【C++】待修改

include <fstream> include <string> include <iostream> include <map>

分手后的思念是犯贱/ 2023年09月23日 16:03/ 0 赞/ 15 阅读

相关 C. Barcode --待补思路

[ https://codeforces.com/contest/225/problem/C][https_codeforces.com_contest_225_probl

以你之姓@/ 2023年01月22日 05:59/ 0 赞/ 2 阅读

相关订单库存回补方案与实现思路

一、思路 1.如何回补？记录需要回补的数据，进行回补。 2.记录什么数据？单出入库分为两个阶段：A.订单解析获取要扣减的库存。B.扣减库存。所以我们按这两个阶段，分两种

约定不等于承诺〃/ 2022年12月08日 05:59/ 0 赞/ 185 阅读

相关 Linux c/c++面试记录（待补充）

1，首先项目介绍； 2，面试问答：操作系统：（1）进程间通信的方式有哪几种，线程间通信的方式又有那几种？（2）说说进程和线程的区别（3）进程间数据是怎么分段的

川长思鸟来/ 2022年11月19日 05:29/ 0 赞/ 251 阅读

相关思路速记待完善

data() { return { list: [ { page: 1,

深碍√TFBOYSˉ_/ 2022年10月10日 09:44/ 0 赞/ 229 阅读

相关条形码+文字生成（barcode)

文章目录背景介绍思路说明具体实现方式 1、添加maven依赖

比眉伴天荒/ 2022年05月15日 14:44/ 0 赞/ 613 阅读

相关 java 处理 barCode(条形码)

【转】java 处理 barCode(条形码) 生成条形码： 1.下载压缩包barcode4j-2.0alpha2-bin.zip和barcode4j-2.0alph

梦里梦外;/ 2022年01月21日 00:29/ 0 赞/ 601 阅读

相关因为工作，急需待补的东西（笔记）

1 web.xml中的filter的写法，特别是它是如何被调用和调用别人的，被调用者包括filter和serlvet。 2 tomcat 工程布置和配置手册。 3 or

野性酷女/ 2022年01月09日 06:51/ 0 赞/ 165 阅读

相关 2016女生专场 ABCDEF题解其他待补...

GHIJ待补... A.HUD5702:[Solving Order][] Time Limit: 2000/1000 MS (Java/Others) Memo

ゝ一纸荒年。/ 2021年12月15日 08:04/ 0 赞/ 286 阅读

相关 vim c++补全

弄了个vim对c++的补全，主要参考自： http://vim.wikia.com/wiki/C%2B%2B\_code\_completion 首先确定vim编辑.

痛定思痛。/ 2021年10月15日 10:21/ 0 赞/ 394 阅读