51nod 1055 最长等差数列

Type: 动态规划,双向DP,思维,技巧

题目

N个不同的正整数,找出由这些数组成的最长的等差数列。

例如:1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举)
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14

其中6 8 10 12 14最长,长度为5。

Input

第1行:N,N为正整数的数量(3 <= N <= 10000)。
第2 – N+1行:N个正整数。(2<= A[i] <= 10^9)

Output

最长等差数列的长度。

Input示例

10
1
3
5
6
8
9
10
12
13
14

Output示例

5

题解

数据范围可判是O(N^2)
一开始我一直在想如何把数字,即两个数之间的差用哈希存起来,来方便dp.
然后搜了题解发现是论文题.
被叫做LLAP问题
Length of the Longest Arithmetic Progressio

论文Link:

https://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

论文解释

这道题可以转化为:

给与一个 排过序 的集合set,我们要求这个集合中的最长等差数列的长度.

标重点: 序列是已排好序的
我们设 dp[i][j] 为以下标 i 和 j 两个元素开头的等差序列最长长度.
我们可以创建一个浮标 j 作为等差数列的中间值

初始化一个 i=j-1,k=j+1.

1.如果 set[i]+set[k] < set[j]*2

k++

2.如果 set[i]+set[k] > set[j]*2

i–

如果 set[i]+set[k]=set[j]*2

则构成等差数列,我们只需要让

dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1

如果dp[j][k]=0的话,dp[i][j]直接=3就可以了,因为 i,j,k 三个刚好构成等差数列.否则等于 dp[j][k]+1

计算完以后 i–,k++ 继续计算其他以 j 为第二个点的等差数列

倒序计算,正序反过来即可

另外: 还可以 直接将 dp 数组初始化为 2(因为每个数的等差数列至少为2).
dp[i][j]=dp[j][k]+1

另外有一个小技巧: 如果int的取值范围不大,但是数组要开很大的时候,可以用 short int,比如这道题.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=10000;

short int dp[maxn][maxn];
int Num[maxn],ans,N;

int main(){
    while(~scanf("%d",&N)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;++i){
            scanf("%d",&Num[i]);
        }
        sort(Num,Num+N);
        ans=0;
        for(int j=N-2;j>=1;--j){
            int i=j-1,k=j+1;
            while(k<N&&i>=0){
                if(Num[i]+Num[k]>2*Num[j]){
                    --i;
                }else if(Num[i]+Num[k]<2*Num[j]){
                    ++k;
                }else{
                    dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1;
                    ans=max(ans,(int)dp[i][j]);
                    --i;++k;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

51NOD 1241 特殊的排序

Type:动态规划,思维,最长等差数列(简化)

题目

一个数组的元素为1至N的整数,现在要对这个数组进行排序,在排序时只能将元素放在数组的头部或尾部,问至少需要移动多少个数字,才能完成整个排序过程?
例如:
2 5 3 4 1 将1移到头部 =>
1 2 5 3 4 将5移到尾部 =>
1 2 3 4 5 这样就排好了,移动了2个元素。

给出一个1-N的排列,输出完成排序所需的最少移动次数。

Input

第1行:1个数N(2 <= N <= 50000)。
第2 – N + 1行:每行1个数,对应排列中的元素。

Output

输出1个数,对应所需的最少移动次数。

Input示例

5
2
5
3
4
1

Output示例

2

题解

一开始会想到和逆序数有关,排序就是减少逆序数,所以会想到其中非逆序序列中最长的那个不用变化.

然后可以容易地证明剩余的数只需要移动一次即可到达正确的位置上

比如 12346587
可以发现最长等差整数序列是 12345 而我们需要 12345678
第一次: 1234587 6
第二次: 1234586 7
第三次: 1234567 8
OK,往数列前面放的也一样

那么我们的问题就是如何求最长等差数列(等差为1)了,

因为等差为1,所以我们不难想到:
dp[i] 为数字 i 的最长等差数列.
遍历Num[]数组的时候计算 dp 即可
dp[i]=dp[i-1]+1

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10;

int dp[maxn],N,Num[maxn],max_;

int main(){
    while(cin>>N){
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        max_=1;
        for(int i=1;i<=N;++i){
            cin>>Num[i];
        }
        for(int i=1;i<=N;++i){
            dp[Num[i]]=dp[Num[i]-1]+1;
            max_=max(dp[Num[i]],max_);
            //cout<<i<<" "<<dp[Num[i]]<<endl;
        }
        cout<<N-max_<<endl;
    }
    return 0;
}