d918 - 6. 雨量趨勢 (99全國賽)

domen111

DP，O(n^2)
sma7想到的作法(他自己卻寫不出來)，我居然沒想出來

最長半遞增子序列 L?IS    (我該怎麼稱呼才對呢? 這篇文章就叫他L?IS好了)
dp[ i ]代表長度為i的L?IS裡面最大的數字(盡量使dp最小)

[C++] 純文本查看 復制代碼

#include<cstdio>
#include<vector>
#include<algorithm>
#define INF 99999999
using namespace std;
int n,m,e;
int a[4000],dp[4000];
int main()
{
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
        while(m--)
        {
                scanf("%d",&e);
                for(int i=0;i<=n;i++)
                        dp[i]=INF;
                dp[0]=0;
                for(int i=0;i<n;i++)
                {
                        for(int j=i+1;j>=1;j--)
                        {
                                if(dp[j-1]-e<=a[i])
                                        dp[j]=min(dp[j],max(dp[j-1],a[i]));
                        }
                }
                int ans=0;
                for(int i=0;i<=n;i++)
                        if(dp[i]!=INF)
                                ans=i;
                printf("%d ",ans);
        }
}