当前位置: 首页 > news >正文

【题解】P11459 [USACO24DEC] Its Mooin Time P

其实是套路题。但有段时间没写过闵可夫斯基和优化 \(dp\) 了,记录一下。

先简单回顾一下闵可夫斯基和。点集 \(P\) 与 点集 \(Q\) 的闵可夫斯基和定义为:\(P+Q=\{a+b|a\in P,b\in Q\}\)

对于两个凸包的闵可夫斯基和,有如下性质:

  1. \(P+Q\) 也为凸包。
  2. \(P+Q\) 的边集由 \(P,Q\) 的边按极角排序后连接的结果。

因此对于大小为 \(n\)\(m\) 的两个凸包,我们可以通过 \(O(n+m)\) 的时间复杂度求出它们的闵可夫斯基和。

对于 \((\max,+)\) 卷积和 \((\min,+)\) 卷积,我们也可以通过类似的方式进行优化。

\((\max,+)\) 卷积为例,设 $c_i=\max_{j+k=i}{a_j+b_k} $。

如果 \((i,a_i)\)\((i,b_i)\) 分别构成凸包,它们的闵可夫斯基和即为 \((i,c_i)\) ,那么可以通过如上方法快速求解数组 \(c\)

如何使用闵可夫斯基和优化 \(dp\) ?对于 \(f_{i,j}=\max_{k<j}\{f_{i-1,k}+a_i\}\) 这类的 \(dp\) ,其中 \(i\) 这一维可能是形如 “选择 \(i\) 个物品” 状物。我们可以退一步,将序列 \(dp\) 改为区间 \(dp\) ,然后用 \([l,mid]\)\([mid+1,r]\) 的答案合并得到 \([l,r]\) 的答案。考虑分治,这样合并两段区间的贡献相当于做闵可夫斯基和的过程,总复杂度 \(O(n\log n)\)

回到这一题,由于 \(L\) 固定,我们可以对每个 \(i\) 预先求出 \([i,i+L-1]\) 合并出 MO.. 的答案。设 \(f_{i,j}\) 表示考虑前 \(i\) 位作为 MO.. 的起点,恰好包含 \(j\)MO.. 的答案,那么转移形式与上式类似,只是要求前一个转移点与当前点相差至少 \(L\) 。将 \(dp\) 改为区间 \(dp\) ,设 \(f_{l,r,a1,a2,k}\) 表示考虑第 \(l\)\(r\) 位作为 MO.. 的起点,最左、右端的点离左右端点的距离状态分别为 \(a_1,a_2\) ,至少包含 \(k\)MO.. 的答案。其中,\(a_1,a_2\)\(0/1/2\) 分别表示距离两段距离为 \(0/1/\geq2\) 。合并连段时做类似矩阵乘法,对 \(a_1,a_2\) 做卷积。时间复杂度 \(O(nL^2\log n)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll x=0; bool f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}return f?x:-x;
}
inline void write(ll x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar('0'+x%10);
}
const ll N=300009;
const ll INF=1e18;
ll L,n,c[N],a[N];
ll g[10][10];
string s;
struct Node{vector<ll> f[3][3];
};
vector<ll> merge(vector<ll> a,vector<ll> b){for(ll i=a.size()-1;i>=2;i--) a[i]-=a[i-1];for(ll i=b.size()-1;i>=2;i--) b[i]-=b[i-1];vector<ll> c(a.size()+b.size()-1);c[0]=a[0]+b[0];merge(a.begin()+1,a.end(),b.begin()+1,b.end(),c.begin()+1);for(ll i=1;i<a.size()+b.size()-1;i++){c[i]+=c[i-1];}return c;
}
void add(vector<ll>&x,vector<ll> y){while(x.size()<y.size()) x.push_back(INF);for(ll i=0;i<y.size();i++) x[i]=min(x[i],y[i]);
}
Node solve(ll l,ll r){if(r-l+1<=2*L){Node res;for(ll x=0;x<L;x++){for(ll y=0;y<L;y++){memset(g,0x3f,sizeof(g));for(ll i=l+x;i<=r-y;i++){g[i-l+1][1]=a[i];if(i-L>=l){for(ll j=2;j<=r-l+1;j++){g[i-l+1][j]=min(g[i-l+1][j],g[i-l+1-L][j-1]+a[i]);}}for(ll j=1;j<=r-l+1;j++){g[i-l+1][j]=min(g[i-l+1][j],g[i-l][j]);}}vector<ll> cur; cur.push_back(0);for(ll i=1;i<=r-l+1;i++){ll mn=INF;for(ll j=l;j<=r;j++){mn=min(mn,g[j-l+1][i]);}if(mn>=INF) break;cur.push_back(mn);}res.f[x][y]=cur;}}return res;}ll mid=(l+r)/2;auto ls=solve(l,mid),rs=solve(mid+1,r);Node res;for(ll i=0;i<=L-1;i++){for(ll j=0;j<=L-1;j++){for(ll mid=0;mid<=L-1;mid++){add(res.f[i][j],merge(ls.f[i][mid],rs.f[L-1-mid][j]));}}}return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>L>>n;cin>>s; s=" "+s;for(ll i=1;i<=n;i++){cin>>c[i];}for(ll i=1;i<=n-L+1;i++){if(s[i]!='M') a[i]=c[i];for(ll j=i+1;j<=i+L-1;j++){if(s[j]!='O') a[i]+=c[j];}}Node res=solve(1,n-L+1);for(ll i=1;i<=n/L;i++){cout<<res.f[0][0][i]<<"\n";}return 0;
}
http://www.hskmm.com/?act=detail&tid=27547

相关文章:

  • 创建一个springboot项目,mybatis连接嵌入式数据库H2,实现增删改查功能
  • 基于众包的产品质量比较与推荐算法研究
  • 10/9
  • 2025.10.9
  • 线程池总结
  • 合并两个有序链表
  • 深入解析:一款相机是只有桶形畸变 和 枕形畸变的一种,还是两个都有?
  • 数据结构-链表
  • 重组抗体技术:从原理到应用,解锁高效可控的新一代抗体研发
  • P13690 [CEOI 2025] boardgames
  • CSS
  • 关于jinja2的ssti模版注入的学习+过滤
  • WPF Epplus export 10M+ items in excel with multiple sheets batch by batch
  • [EGOI 2023] Guessing Game
  • CF2152G Query Jungle
  • [ROI 2018] Addition without carry
  • [THUPC 2025 决赛] Im Here
  • 解码Linux基础命令
  • 基于 C++ 的高雷诺数湍流直接数值模拟求解器设计与性能优化 - 实践
  • 由等概率(a,b)生成等概率(c,d)
  • AI/LLM应用安全与合规产品(AI安全网关|AI安全围栏|AI应用防火墙) 2025最新推荐
  • 10.8 CSP-S模拟27 改题记录
  • 《可复制的领导力》
  • 经营分析会 - 智慧园区
  • 自动评估问答模型的技术突破
  • Ivanti EPM移动版12.5.0.0身份验证绕过漏洞分析与利用
  • 运行Udacity的MPC控制项目指南(project_10)在Ubuntu 18.04环境下
  • 深入解析:Java 将 PDF 转换为 PDF/A:数字文档归档的基石
  • 入门正当时!MQTT协议轻量简洁,但应用绝不简单
  • 英语阅读