最少拦截系统

HDOJ-1257

我做这题的思路就是采用暴力或者贪心。也就是每次循环选出从第一个未被选择的元素开始，依次把后面可以选择的元素作为一个系统。最后统计可以有多少个系统。
还有人的思路就是利用动态规划的思路，求解最长上升子序列，也就是反着题意来求。因为在这个最长上升子序列中，所有的元素不可能在同一个拦截系统中，所以子序列的长度就是最后的答案，也就是拦截系统的个数
https://blog.csdn.net/qq_29963431/article/details/49081409
还有博客介绍的方法相对我的解题思路来说上了一个台阶，使用了优化，每次记录一个拦截系统中以后可以拦截的最高度。https://blog.csdn.net/hurmishine/article/details/52926957

//最长上升子序列的变形

#include<bits/stdc++.h>

using namespace std;

const int INF=0X3F3F3F3F;

const int maxn=1e6;

int n;

int height[maxn];

bool vis[maxn];

int main(){

    while(cin>>n){

        for(int i=1;i<=n;i++){

            cin>>height[i];

        }

        int ans=0;

        memset(vis,0,sizeof(vis));

        for(int i=1;i<=n;i++){

            bool flag=false;

            int pre=INF;

            for(int j=1;j<=n;j++){

                if(!vis[j]&&pre>height[j]){

                    flag=true;

                    vis[j]=true;

                    pre=height[j];

                }

            }

            if(flag)

                ans++;

        }

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

HDOJ-1257(贪心/动态规划)

最少拦截系统

HDOJ-1257

最新文章

热门文章