查看: 633|回復: 0

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

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-10-16 17:51:22 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    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);
            }
    }
    

    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表