题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=17
题目分析:这是基本题,没什么好分析的。只有把基础算法烂熟于心,才能更好的应付那些算法的变种。
相关题目链接:http://blog.csdn.net/kay_zhyu/article/details/8714581
http://blog.csdn.net/kay_zhyu/article/details/8713068
#include<stdio.h> #include<string.h> char str[10000]; int dp[10000]; int max(const int a, const int b) { return a > b ? a : b; } int DP(int n) { int i,j; dp[0] = 1; int ans = 1; for(i = 1; i < n; ++i) { dp[i] = 1; for(j = 0; j < i; ++j) { if(str[j] < str[i]) dp[i] = max(dp[i],dp[j] + 1); } ans = max(ans,dp[i]); } return ans; } int main() { int t,nLen; int i,k; int ans; scanf("%d",&t); getchar(); while(t--) { gets(str); nLen = strlen(str); ans = DP(nLen); printf("%d\n",ans); } }