其实就是求单调最长不降子序列的个数，这题有很多方法，有用map的，有字典树的，我的方法很简单，标记搜索，提交不要选g++，会被卡超时，选c++即可。
[cpp] #include #include #include #include #include #include using namespace std; int level[3010]; bool visit[3010]; bool cmp(int a,int b){ return a>b; } int main() { int n; while(cin>>n) { for(int i=0;i scanf("%d",&level[i]); memset(visit,0,sizeof(visit)); sort(level,level+n,cmp); int sum=0; for(int i=0;i { if(visit[i])continue; int k=i; for(int j=0;j { if(visit[j])continue; if(level[j] visit[j]=1; k=j; } } sum++; visit[i]=1; } cout< } return 0; }
#include #include #include #include #include #include using namespace std; int level[3010]; bool visit[3010]; bool cmp(int a,int b){ return a>b; } int main() { int n; while(cin>>n) { for(int i=0;i scanf("%d",&level[i]); memset(visit,0,sizeof(visit)); sort(level,level+n,cmp); int sum=0; for(int i=0;i { if(visit[i])continue; int k=i; for(int j=0;j { if(visit[j])continue; if(level[j] visit[j]=1; k=j; } } sum++; visit[i]=1; } cout< } return 0; }