首页 > 代码库 > BZOJ 4576: [Usaco2016 Open]262144
BZOJ 4576: [Usaco2016 Open]262144
Description
一个序列,每次可以将两个相同的数合成一个数,价值+1,求最后最大价值 \(n \leqslant 262144\)
Sol
DP.
这道题是 BZOJ 4580: [Usaco2016 Open]248 加强版.
做248的那个区间DP其实很多方案都是0,而且一个区间中只有一个合法的数字.
然后就是 一个区间合成一个数的方案的这个数字是固定的.
\(f[i][j]\) 表示以 \(i\) 结尾是否能合成 \(j\),同时记录一下转移位置,每次向前找前一个指针就可以了.
复杂度 \(O(nm)\)
Code
/************************************************************** Problem: 4576 User: BeiYu Language: C++ Result: Accepted Time:1208 ms Memory:79368 kb****************************************************************/ #include <cstdio>#include <iostream>using namespace std; const int N = 263005;const int M = 60; int n,ans,a[N];bool f[N][M];int g[N][M]; inline int in(int x=0){ scanf("%d",&x);return x; }int main(){ n=in(); for(int i=1;i<=n;i++) a[i]=in(); for(int i=1,p;i<=n;i++){ p=i-1,f[i][a[i]]=1,g[i][a[i]]=i; ans=max(ans,a[i]); for(int j=a[i];j<M;j++){ if(f[p][j]) f[i][j+1]=1,g[i][j+1]=g[p][j],p=g[p][j]-1,ans=max(ans,j+1); else break; } }// for(int i=1;i<=n;i++) for(int j=1;j<6;j++) cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<g[i][j]<<endl; cout<<ans<<endl; return 0;}
BZOJ 4576: [Usaco2016 Open]262144
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。