题解 P2501 【[HAOI2006]数字序列】

smzzl · 2019-01-05 15:23:14 · 题解

这里分享一个第一问的解法

本蒟蒻想不到这种做法下的第二问解法（只想到n^3的）。

欢迎各dalao在评论区反应，欢迎dalao分享在我这个第一问思路基础上的第二问解法（或者第一问的优化到nlogn方式）。

本算法是一个很不优秀的做法，但是没有看到题解里有这种做法的，想和大家分享一下。

以下是我第一问思路

设 d[i][k] 表示在第 i 位时候，使用 k 次修改的最小末尾，于是就有了一个转移方程：

1：d[i][k]=a[i] (a[i]>d[i-1][k])

2: d[i][k]=d[i-1][k-1]+1 (k>=1)

1，2两式子取min

方程解释：

对于1表示如果这位原数的值大于了上一位修改k次的最小末尾，那么这一位就可以不花代价的直接填下。

对于2表示把这位的数值调到最接近上一位最小数值的值（上一位的值+1，以保证严格上升）（贪心思想：对于每个k，末尾一定是越小越好）

于是第一问就做完了，时间复杂度为接近n^2，6000稳过，由于常数小在开启o2后能够通过所有点的第一问。

以下是我的代码，欢迎dalao们指出错误。

#include<iostream>
#define inf 99999999999
using namespace std;
long long n;
long long a[200005],d[2][35002];//滚动数组

inline long long _min(long long a1,long long a2){return (a1<a2)?a1:a2;}
int main()
{
    cin>>n;
    for (long long i=1;i<=n;i++) cin>>a[i];
    d[0&1][0]=-inf; d[0][1]=inf;//初值 

    for (long long i=1;i<=n;i++)
        {
            for (long long k=0;k<=i;k++) d[i&1][k]=inf;
            //初始化无穷大 
            if (d[(i-1)&1][0]<a[i]) d[i&1][0]=a[i];
            //对于k=0由于不能执行转移2，于是我们先做掉 
            for (long long k=1;k<=i;k++) {
                if (a[i]>d[(i-1)&1][k]) d[i&1][k]=a[i];//转移1 
                d[i&1][k]=_min(d[i&1][k],(d[(i-1)&1][k-1])+1);//转移2 
            }

        }
    long long ans=inf;  
    for (long long k=0;k<=35002;k++) 
        if (d[n&1][k]<inf) {ans=k; break;}
    //找到一个不是inf的就是解 
    cout<<ans;
}