POJ3276 Face The Right Way 开关问题
2024-10-08 18:09:47
①每个K从最左边进行考虑
②f[i]=[i,i+k-1]是否进行反转:1代表是,0代表否
③∑ (i)(i=i+1-K+1) f[j]=∑ (i-1)(i=i-K+1) f[j]+f[i]-f[i-K+1]
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
using namespace std;
int n;
int dir[],f[];//dir牛的方向0F1B,f是[i,i-k+1]是否反转
int cal(int k)//k求最小操作数
{
memset(f,,sizeof(f));
int res=;
int sum=;//f的和
for(int i=;i+k<=n;i++)
{
if((dir[i]+sum)%!=)
{
res++;
f[i]=;
}
sum+=f[i];
if(i-k+>=)
{
sum-=f[i-k+];
}
}
//检查后面的牛有没有朝后
for(int i=n-k+;i<n;i++)
{
if((dir[i]+sum)%!=)
{
return -;//无解
}
if(i-k+>=)
{
sum-=f[i-k+];
}
}
return res;
}
void solve()
{
int resK=,resM=n;
for(int k=;k<=n;k++)
{
int m=cal(k);
if(m>=&&resM>m)
{
resM=m;
resK=k;
}
}
printf("%d %d\n",resK,resM);
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
getchar();
char c=getchar();
if(c=='B')
dir[i]=;
else
dir[i]=;
}
solve();
return ;
}
最新文章
- C# 随机红包算法
- 关于斐波拉契数列(Fibonacci)
- 模糊搜索UISearchBar
- 慕课网-安卓工程师初养成-2-7 Java中变量的使用规则
- C#下如何用NPlot绘制期货股票K线图(3):设计要显示的股票价格图表窗口并定义相应类的成员及函数
- ServletContext对象--三大域对象
- Minimum Size Subarray Sum 解答
- C++编程练习(12)----“有向图的拓扑排序“
- axis调用webservice的简单方法
- vue组件路由守卫钩子函数(beforeRouteEnter、beforeRouteUpdate、beforeRouteLeave)
- 做seo应该如何选择网站程序?
- bsdiff的编译与使用
- Django Web开发学习笔记(5)
- hive中安装hive_utils模块
- 学习笔记14—Python error集
- Spring Cloud(Dalston.SR5)--Eureka 服务实例健康检查
- caffe中的学习率的衰减机制
- 基于JS实现发送短信验证码后的倒计时功能(无视页面刷新,页面关闭不进行倒计时功能)
- shell编程——流控制case和select
- &#39;node&#39; 不是内部或外部命令,也不是可运行的程序或批处理文件
热门文章
- 牛逼了,用Python破解wifi密码
- shell字符串大小写转换
- .NET技术-6.0. Expression 表达式树 生成 Lambda
- PAT Advanced 1123 Is It a Complete AVL Tree (30) [AVL树]
- Python 重新加载模块
- 洛谷P1002 过河卒(动态规划)
- ubuntu服务器上配置tomcat
- Linux(CENTOS7) Nginx负载均衡简单配置
- 线性可分支持向量机与软间隔最大化--SVM(2)
- 吴裕雄--天生自然 PHP开发学习:魔术常量