Blog·Tanky WooABOUTRSS

HDOJ 1257 最少拦截系统

10 Jan 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

终于回到家了,万恶的期末考试也结束了,这次期末考试比较有纪念意义,因为我考到了读书15年来的最低分----《检测技术与装置》考了33分=。=

好吧,开学得去补考,废话不多说,拿水题来开刀!

注意此题要逆向思考

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1257

标准的LIS(最长上升子序列)题目,我用的是O(n^2)的方法。

LIS算法详细讲解见http://www.wutianqi.com/?p=1850

#include 
using namespace std;

int arr[1005];
int dp[1000];

int LIS(int *arr, int n)
{
    for(int i=1; i<=n; ++i)
        dp[i] = 0;
    int ans;
    dp[1] = 1;
    for(int i=2; i<=n; ++i)
    {
        ans = dp[i];
        for(int j=1; jarr[j] && dp[j]>ans)
                ans = dp[j];
        }
        dp[i] = ans+1;
    }
    ans = 0;
    for(int i=1; i<=n; ++i)
    {
        if(dp[i] > ans)
            ans = dp[i];
    }
    return ans;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    while(scanf("%d", &n;) != EOF)
    {
        for(int i=1; i<=n; ++i)
            cin >> arr[i];
        cout << LIS(arr, n) << endl;
    }
    return 0;
}