觉得我的这两种思路都没问题也可以过样例但竟0分
  • 板块P3392 涂国旗
  • 楼主YOUNGxy
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/20 21:16
  • 上次更新2023/12/21 11:42:40
查看原帖
觉得我的这两种思路都没问题也可以过样例但竟0分
1087763
YOUNGxy楼主2023/12/20 21:16
#include<bits/stdc++.h>
using namespace std;
#define LEN 50
int n,m;
int ans=999999;
vector<int> a[LEN];

void dfs(int step,int cur,int sum)
{
    if(step==n)
    {
        if(cur==2) ans=min(ans,sum);
    }
    else for(int i=0;i<=1&&cur+i<=2;i++)//每次拓展只有两种选择 
        dfs(step+1,cur+i,sum+a[step][cur+i]);
}

signed main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)//对每行预处理出删去各颜色需要涂的格子数
    {
        int w=0,b=0,r=0;
        getchar();
        for(int j=0;j<m;j++)
        {
            char t=getchar();
            switch(t)
            {
            case 'W':
                w++;
                break;
            case 'B':
                b++;
                break;
            case 'R':
                r++;
                break;
            }
        }
        a[i].push_back(m-w);//0 1 2分别对应白蓝红
        a[i].push_back(m-b);
        a[i].push_back(m-r);
    }
    //第一种深搜的思路
    // dfs(1,0,a[0][0]);//第一行一定只能选涂白色
    //第二种思路
    for(int i=1;i<n;i++)//白格子的数量
    {
        for(int j=1;i+j<n;j++)//蓝格子的数量
        {
            int t=0;
            int k=n-(i+j);
            int i1=i,j1=j;
            while(k) t+=a[(i1+j1)+(--k)][2];
            while(j1) t+=a[i1+(--j1)][1];
            while(i1) t+=a[--i1][0];
            ans=min(ans,t);
        }
    }

    cout<<ans;

    return 0;
}
2023/12/20 21:16
加载中...