hdu 1800 Flying to the Mars

传送门
本质：判断出现最多的那个数字的次数是多少
①trie

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int res;
int son[N][11],cnt[N],idx;
void insert(char str[])
{
	int p=0;
	while(*str=='0')str++;//去掉前导0 
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'0';
		if(!son[p][u])son[p][u]=++idx;
		p=son[p][u];
	}
	if(++cnt[p]>res)res=cnt[p];
} 
int main()
{
	int n;
	char str[35];
	while(~scanf("%d",&n))
	{
		memset(son,0,sizeof son);
		memset(cnt,0,sizeof cnt);
		idx=0;
		int i;
		for(i=0,gets(str),res=1;i<n;i++)//这里gets是为了吸收掉回车
			scanf("%s",str),insert(str);
		printf("%d\n",res);
	}
}

②字符串哈希

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e4+10;
int h[N],cnt[N]; 
int BKDR(char *str)
{
	int seed=131;
	unsigned long long hash=0;
	while(*str)
		hash=hash*seed+(*str++);
	return hash&0x7fffffff;
}
int res;
void op(char  *str)
{
	int k,t;
	while(*str=='0')str++;
	k=BKDR(str),     t=k%N;
	while(h[t]!=k&&h[t]!=-1)
		t=(t+10)%N;
	if(h[t]==-1)cnt[t]=1,h[t]=k;
	else if(++cnt[t]>res) res=cnt[t];
}
int main()
{
	char str[100];
	int n;
	while(~scanf("%d",&n))
	{
		memset(h,-1,sizeof h);
		for(res=1,gets(str);n>0;n--)
			gets(str),op(str);
		printf("%d\n",res);
	}
}

③用最长上升子序列的方法去贪心

#include<iostream>
#include<algorithm>
using namespace std;
const int N=3010;
int main()
{
    int n;
    while(cin>>n)
    {
        int cnt=0;
        int w[n+10]={0};
        int q[n+10]={0};
        for(int i=0;i<n;i++)scanf("%d",&w[i]);
        sort(w,w+n);
        for(int i=0;i<n;i++)
        {
            int k=0;
            while(k<cnt&&q[k]>=w[i])k++;
            if(k==cnt)q[cnt++]=w[i];
            else q[k]=w[i];
        }
        printf("%d\n",cnt);
    }
}