2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest E:Black or White
2024-08-30 12:26:20
这道题可以比较容易看出是线性DP。设dp[i]代表把前i个格子刷成目标状态的最小步数。
写出状态转移方程 dp[i]=min( dp[j]+calc(j+1,i) ) (i-j<=k) calc(j+1,i)代表把区间 [j+1,i] 的块刷成目标状态的最小代价。
那么问题在于怎么算calc(j+1,i)。这里直接给出结论:calc=(s[i]-s[j])/2+1,意思是最小代价是先把区间[j+1,i]刷成段数比较多的那种颜色,然后再一段一段把段数较小的刷好。代价就是1+(s[i]-s[j])/2。
把方程拆开 2*f[i]=2*f[j]+s[i]-s[j]+2 f[i]=(s[i]+(2*f[j]-s[j])+2) / 2
观察式子发现只有 2*f[j]-s[j] 跟j相关,并且j的取值上下界都在变化。容易想到用单调队列优化。
这里还要主要一个小细节:例如 BBBWWW 那么s的值就是 111222 。此时s[5]-s[2]=1,事实上[3,4,5]这一段应该是两段组成,s[5]-s[2]应该等于2 。
所以要加入 if (s[i]==s[i+1]) s[i]--; 这一句代码。意思是i点还不是该段结尾点,i+1及后面还会有这一段的残余,然后令s[i]-1使得后面的s[p]减去s[i]的时候会算上这一段残余段(比较难表达,但就是这个意思qwq)。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+;
int n,k,f[N],s[N],q[N];
char A[N],B[N]; int calc(int j) { return *f[j]-s[j]; } int main()
{
cin>>n>>k;
scanf("%s",A+); scanf("%s",B+);
for (int i=;i<=n;i++) if (B[i]!=B[i-]) s[i]=;
for (int i=;i<=n;i++) s[i]+=s[i-]; int h=,t=; q[]=;
for (int i=;i<=n;i++) {
while (h<=t && i-q[h]>k) h++;
if (h<=t) f[i]=(s[i]+calc(q[h])+)/;
if (A[i]==B[i]) f[i]=f[i-];
if (s[i]==s[i+]) s[i]--; //这一句很重要
while (h<=t && calc(i)<=calc(q[t])) t--;
q[++t]=i;
}
cout<<f[n]<<endl;
return ;
}
最新文章
- IDEA构建一个mybatis项目
- iOS-不用网线搭建IPv6网络测试环境
- C++11特性(模板类 initializer_list)
- 手机APP功能测试经验分享2016.06.06
- C# 异常处理 <;->; 连接远程数据库遇到的问题
- Java 第一课
- ruby -- 问题解决(四)编码错误导致无法显示(2)
- jQuery时间轴插件:jQuery Timelinr
- linux C 管道
- Java串口通信详细解释
- linux命令readlink
- php获取当前文件绝对路径
- Swashbuckle Swagger组件扩展
- 对JDBC的优化,BeanUtils和DBUtils
- Android ec环境配置
- 陈敏 Java课设实验报告
- js高级:event,事件冒泡,事件捕获
- ASP.NET MVC5高级编程 之 Ajax
- 使用Lifecycle管理Tomcat中组件的生命周期
- Android稳定性测试工具Monkey的使用