洛谷 P3287 - [SCOI2014]方伯伯的玉米田(BIT 优化 DP)
怎么题解区全是 2log 的做法/jk,这里提供一种 1log 并且代码更短(bushi)的做法。
首先考虑对于一个序列 \(a\) 怎样计算将其变成单调不降的最小代价。对于这类涉及区间操作问题,果断往差分序列方向想,我们记 \(d_i=a_i-a_{i+1}\),那么我们肯定会想将所有 \(d\) 都变成非正的,而一次操作肯定会将某个 \(d_i\) 减 \(1\),并选择将某个 \(d_i\) 加 \(1\)(当然也可以不操作)。加一肯定是不优的,因此我们每次肯定会选择最右边的元素作为右端点避免加一操作。因此将序列 \(d\) 变成非正的代价就是 \(\sum\max(d_i,0)\)。
接下来就可以考虑 DP 了。我们设 \(dp_{i,j}\) 表示序列最后一个元素是 \(a_i\),当前 \(\sum\max(d_i,0)=j\) 最多保留了多少株玉米。那么有转移 \(dp_{i,j}=\max\limits_{l<i}dp_{l,j-\max(a_l-a_j,0)}+1\)。直接转移是 \(n^2k\) 的。不过注意到这题的值域很小,因此考虑将 \(\max\) 然后 BIT 处理偏序关系,具体来说,如果 \(a_l<a_j\),那么 \(dp_{l,j}+1\to dp_{i,j}\),我们就建立 \(k\) 个树状数组,第 \(j\) 个下标为 \(t\) 的位置维护 \(a_l=t\) 的 \(l\) 中 \(dp_{l,j}\) 的最大值,那么这一类转移就在第 \(j\) 个树状数组中取一遍前缀 \(\max\) 即可。如果 \(a_l\ge a_j\),那么 \(dp_{l,j-a_l+a_j}+1\to dp_{l,j}\)。不难发现这一类 DP 转移来的 \(dp_{l,t}\) 一定有 \(t+a_l=j+a_i\),于是我们建立 \(5500\) 个 BIT,第 \(i\) 个下标为 \(j\) 的位置维护 \(t+a_l=i,a_l=j\) 的 \(dp_{l,t}\) 的最大值,这样这一类 DP 转移即可写成后缀和的形式,也可 BIT 维护。
复杂度 \(nk\log n\)。
const int MAXN=10000;
const int MAXK=500;
const int MAXV=5000;
int n,k,a[MAXN+5];
struct fenwick{
int t[MAXV+5];
void add(int x,int v){for(int i=x;i<=MAXV;i+=(i&(-i))) chkmax(t[i],v);}
int query(int x){int ret=0;for(int i=x;i;i&=(i-1)) chkmax(ret,t[i]);return ret;}
} t1[MAXK+MAXV+5],t2[MAXV+5];
int main(){
scanf("%d%d",&n,&k);int res=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
int val=max(t1[j+a[i]].query(MAXV-a[i]+1),t2[j].query(a[i]))+1;
t1[j+a[i]].add(MAXV-a[i]+1,val);t2[j].add(a[i],val);chkmax(res,val);
}
} printf("%d\n",res);
return 0;
}
最新文章
- MYsql 数据库密码忘记(Linux)
- svchost占用cpu
- 20145213《Java程序设计》第十周学习总结
- PAT (Basic Level) Practise:1023. 组个最小数
- arpg网页游戏之地图(四)
- IOS项目集成ShareSDK实现第三方登录、分享、关注等功能。
- 转载 ASP.NET常用的正则表达式
- 如何使用iOS 8 指纹识别,代码、示例
- Python系列教程(三):输入和输出
- Cocos Creator—最佳构建部署实践
- 将多张图片打包成zip包,一起上传
- Scrapy实战篇(二)之爬取链家网成交房源数据(下)
- 前端组件化Polymer入门教程(5)——生命周期
- mongodb如何设置主键自增
- python学习之老男孩python全栈第九期_数据库day004 -- 作业
- 【BestCoder】【Round#41】
- UVa 10905 - Children&#39;s Game(求多个正整数排列后,所得的新的数字的极值)
- 向量与矩阵的范数及其在matlab中的用法(norm)
- 【UOJ 34】 多项式乘法 (FFT)
- cannot resolve symbol AppCompatActivity 心得