HDOJ 1257 最少拦截系统

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

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

注意此题要逆向思考

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
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; j<i; ++j)
        {
            if(arr[i]>arr[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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1257 最少拦截系统》有18个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注