您的位置:

java实现单调数列(单调递增的数字java)

本文目录一览:

单调队列怎么用java实现

单调队列是一种严格单调的队列,可以单调递增,也可以单调递减。队首位置保存的是最优解,第二个位置保存的是次优解,ect。。。

单调队列可以有两个操作:

1、插入一个新的元素,该元素从队尾开始向队首进行搜索,找到合适的位置插入之,如果该位置原本有元素,则替换它。

2、在过程中从队首删除不符合当前要求的元素。

单调队列实现起来可简单,可复杂。简单的一个数组,一个head,一个tail指针就搞定。复杂的用双向链表实现。

用处:

1、保存最优解,次优解,ect。

2、利用单调队列对dp方程进行优化,可将O(n)复杂度降至O(1)。也就是说,将原本会超时的N维dp降优化至N-1维,以求通过。这也是我想记录的重点

是不是任何DP都可以利用单调队列进行优化呢?答案是否定的。

记住!只有形如 dp[i]=max/min (f[k]) + g[i] (ki g[i]是与k无关的变量)才能用到单调队列进行优化。

优化的对象就是f[k]。

通过例题来加深感受

我要长高

Description

韩父有N个儿子,分别是韩一,韩二…韩N。由于韩家演技功底深厚,加上他们间的密切配合,演出获得了巨大成功,票房甚至高达2000万。舟子是名很有威望的公知,可是他表面上两袖清风实则内心阴暗,看到韩家红红火火,嫉妒心遂起,便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力,随口一句便会造成韩家的巨大损失,具体亏损是这样计算的,韩一,韩二…韩N站成一排,损失即为C*(韩i与韩i+1的高度差(1=iN))之和,搞不好连女儿都赔了.韩父苦苦思索,决定给韩子们内增高(注意韩子们变矮是不科学的只能增高或什么也不做),增高1cm是很容易的,可是增高10cm花费就很大了,对任意韩i,增高Hcm的花费是H^2.请你帮助韩父让韩家损失最小。

Input

有若干组数据,一直处理到文件结束。 每组数据第一行为两个整数:韩子数量N(1=N=50000)和舟子系数C(1=C=100) 接下来N行分别是韩i的高度(1=hi=100)。

首先建立方程,很容易想到的是,dp[i][j]表示第 i 个儿子身高为 j 的最低花费。分析题目很容易知道,当前儿子的身高花费只由前一个儿子影响。因此,

dp[i][j]=min(dp[i-1][k] + abs(j-k)*C + (x[i]-j)*(x[i]-j));其中x[i]是第i个儿子原本的身高

我们分析一下复杂度。

首先有N个儿子,这需要一个循环。再者,每个儿子有0到100的身高,这也需要一维。再再者,0到100的每一个身高都可以有前一位儿子的身高0到100递推而来。

所以朴素算法的时间复杂度是O(n^3)。题目只给两秒,难以接受!

分析方程:

当第 i 个儿子的身高比第 i-1 个儿子的身高要高时,

dp[i][j]=min(dp[i-1][k] + j*C-k*C + X); ( k=j ) 其中 X=(x[i]-j)*(x[i]-j)。

当第 i 个儿子的身高比第 i-1 个儿子的身高要矮时,

dp[i][j]=min(dp[i-1][k] - j*C+k*C + X); ( k=j )

对第一个个方程,我们令 f[i-1][k]=dp[i-1][k]-k*C, g[i][j]=j*C+X; 于是 dp[i][j] = min (f[i-1][k])+ g[i][j]。转化成这样的形式,我们就可以用单调队列进行优化了。

第二个方程同理。

接下来便是如何实现,实现起来有点技巧。具体见下

View Code

还有一个比较适合理解该优化方法的题目是HDU 3401

大概题目便是:一个人知道接下来T天的股市行情,想知道最终他能赚到多少钱。

构造状态dp[i][j]表示第i 天拥有 j只股票的时候,赚了多少钱

状态转移有:

1、从前一天不买不卖:

dp[i][j]=max(dp[i-1][j],dp[i][j])

2、从前i-W-1天买进一些股:

dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])

3、从i-W-1天卖掉一些股:

dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])

这里需要解释一下为什么只考虑第i-W-1天的买入卖出情况即可。想想看,i-W-2天是不是可以通过不买不卖将自己的最优状态转移到第i-W-1天?以此类推,之前的都不需要考虑了,只考虑都i-W-1天的情况即可。

对买入股票的情况进行分析,转化成适合单调队列优化的方程形式

dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i],则dp[i][j]=max(f[i-W-1][k]) - j*AP[i]。

这便可以用单调队列进行优化了。卖股的情况类似分析。

View Code

最后再说一个应用,用单调队列来优化多重背包问题 hdu 2191

如果有n个物品,每个物品的价格是w,重量是c,且每个物品的数量是k,那么用这样的一些物品去填满一个容量为m的背包,使得得到的背包价值最大化,这样的问题就是多重背包问题。

对于多重背包的问题,有一种优化的方法是使用二进制优化,这种优化的方法时间复杂度是O(m*∑log k[i]),具体可以见

而利用单调队列的优化,复杂度是O(mn)

首先,对于第i件物品,如果已知体积为V,价值为W,数量为K,那么可以按照V的余数,将当前的体积J分成V组(0,1,....V-1)。

对于任意一组,可以得到转移方程:f[i*V+c]=f[k*V+c]+(i-k)*W,其中c是V组分组中的任意一个

令f[i*V+c]=dp[i],那么就得到dp[i]=dp[k]+(i-k)*W (k=i-K)

将dp[k]-k*W看做是优化函数,那么就可以运用单调队列来优化了

java编程实现输出fibonacci数列(要求利用数组实现)的前30项

这个问题没有难度吧。写了一下你参考下,循环 递归都能轻松实现的。

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] fibonacci=null;

fibonacci=fibonacci(30);

System.out.println(Arrays.toString(fibonacci));

fibonacci=new int[30];

fibonacci(fibonacci,0);

System.out.println(Arrays.toString(fibonacci));

}

//循环

public static int[] fibonacci(int length){

int[] fibonacci=new int[length];

fibonacci[0]=0;

fibonacci[1]=1;

for(int i=2;ilength;i++)

fibonacci[i]=fibonacci[i-1]+fibonacci[i-2];

return fibonacci;

}

//递归

public static void fibonacci(int[] fibonacci,int index){

if(index-1indexfibonacci.length){

    if(index2index-1)

     fibonacci[index]=index;

    else

    fibonacci[index]=fibonacci[index-1]+fibonacci[index-2];

    fibonacci(fibonacci,index+1);

}

}

java如何生成一组随机的不重复的数列?

把源数据放到数组中,然后循环随机交换这个数组元素的位置就可以了

int[]aa = {1,2,5,6,8,9,7};

Random r = new Random();

for(int i=0;i100;i++)

{

int index = r.nextInt(aa.length);

int temp = aa[0];

aa[0] = aa[index];

aa[index] = temp;

}