首页 > 代码库 > TYVJ1113

TYVJ1113

2024-07-19 06:38:03   219人阅读

其实就是最长上升子序列。
只要把普通的LIS中的“>”改为另外一种这里需要的判断的方式即可。
dp[i]表示包含i在内的从1到i的LIS
状态方程， dp[i] = max(dp[i],dp[j]+1)(if(“i>j”));
边界dp[i] = 1;
最后还需要扫一遍dp[]取出其中的最大值，（为什么dp[n]不是最大值？这个我说不清楚，自己思考吧还是）
还有就是这里的“大于”的判断，首先len[i]必须要大于len[j]吧，其次就是从0到len[j]扫一遍两个字符串，只要碰到s[i][k]!=s[j][k]则说明不行。。否则return true！；

还有。。。。一开始我想2000*2000*75可能会超时，而且又不会nlogn。后来尝试敲了交上去，发现也过了，可能数据比较弱吧。

 

 

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 2005; 7 char s[maxn][80]; 8 int len[maxn],dp[maxn]; 9 bool dayu(int i,int j)10 {11     if(len[i]<=len[j])return false;12     for(int k = 0;k<len[j];++k)13         if(s[j][k]!=s[i][k])return false;14     return true;15 }16 int main()17 {18     //freopen("in.txt","r",stdin);19     int n;20     while(cin>>n)21     {22         for(int i = 1;i<=n;++i)23         {24             scanf("%s",s[i]);25             len[i] = strlen(s[i]);26             dp[i] = 1;27         }28         for(int i = 2;i<=n;++i)29         {30             for(int j = 1;j<i;++j)31                 if(dayu(i,j))dp[i] = max(dp[i],dp[j]+1);32         }33         int ans = -1;34         for(int i = 1;i<=n;++i)35             ans = max(ans,dp[i]);36         cout<<ans<<endl;37     }38     return 0;39 }

 

TYVJ1113


联系
我们