hdu 1257/1800 - 贪心，dp

1257题目链接

一个序列划分子序列，每个子序列都是非增序列，问最少分成几个子序列

1800题目链接

一堆数分组，每组内数据严格递减，问最少分几组

------------------------------------------------------------------------------------------------

这两个题的区别在于1257数组的排列顺序不能变，而1800只是分组，顺序随意。

1257有两种解法：

一是像hdu1051那样的贪心：像筛素数那样一个序列一个序列的标记。

一是求最长严格递增序列的长度，动态规划做。

而1800只需要统计每个数字出现的次数，找到最大的出现次数，注意前导0

1257贪心代码，0ms

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

typedef long long LL;

using namespace std;

const int N = ;

int hs[N];

bool vis[N];

int main(){

    int n;

    while(scanf("%d",&n)!=EOF){

        for(int i=;i<n;i++) scanf("%d",hs+i);

        memset(vis,false,sizeof(vis));

        int ans = ;

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

            if(!vis[i]){

                ans++;

                int last = hs[i];

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

                    if((!vis[j])&&hs[j]<=last) last=hs[j],vis[j]=true;

                }

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

1257dp代码，31ms

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

typedef long long LL;

using namespace std;

const int N = ;

int hs[N],dp[N];

int main(){

    int n;

    while(scanf("%d",&n)!=EOF){

        for(int i=;i<n;i++) scanf("%d",hs+i);

        int ans = ;

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

            dp[i]=;

            for(int j=;j<i;j++){

                if(hs[j]<hs[i]) dp[i]=MAX(dp[i],dp[j]+);

            }

            ans = max(ans,dp[i]);

        }

        printf("%d\n",ans);

    }

    return ;

}

1800，用map统计

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

typedef long long LL;

using namespace std;

const int N = ;

int main(){

    int n,id;

    char tmp[];

    map<string,int> strs;

    while(scanf("%d",&n)!=EOF){

        if(!n){puts("");continue;}

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

            scanf("%s",tmp);

            for(id=;id<strlen(tmp);id++){ if(tmp[id]!='') break; }

            if(id==strlen(tmp)) id--;

            if(strs.count(tmp+id)) strs[tmp+id]++;

            else strs[tmp+id]=;

        }

        int ans = ;

        for(map<string,int>::iterator iter=strs.begin();iter!=strs.end();iter++)

            ans = MAX(ans,iter->second);

        printf("%d\n",ans);

        strs.clear();

    }

    return ;

}