257 条题解
-
10
larryzhong LV 9 @ 7 年前
最长上升子序列 (LIS)
-
2
//简单的dp，lcs问题
//使用str查找函数来标记词链是一个巧妙的思路
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int n;
int f[3000];
string s[3000];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
cin>>s[i];
}
for (int i=1;i<=n;i++)
{ f[i]=1;
for (int j=1;j<i;j++)
{
if (s[i].find(s[j])==0)
{
f[i]=max(f[i],f[j]+1);
}
}
}
int ans=-1;
for (int i=1;i<=n;i++)
ans=max(ans,f[i]);
printf("%d",ans);
return 0;
} -
1
#include <iostream> //魔族密码
#include <cstdio>
#include <cstring>
using namespace std;
const int MaxN = 2010;int N;
int dp[MaxN];
char word[MaxN][80];void DP()
{
int max = 1;
char ch = word[0][0];
for (int i = 1; i < N; i++)
{
if (word[i][0] != ch)
{
ch = word[i][0];
continue;
}
for (int j = i - 1; word[j][0] == ch && j >= 0; j--)
if (strstr(word[i], word[j]))
{
dp[i] = dp[j] + 1;
if (max < dp[i])
max = dp[i];
break;
}
}
printf("%d\n", max);
}int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> word[i];
dp[i] = 1;
}DP();
system("pause");
return 0;
} -
1
单调栈做法
```c++
#include <string>
#include <iostream>
#include <stack>
using namespace std;stack<string> s;
string a[1005];
int n,ans=0;bool is_ok(string t)
{
if (s.empty()||t.substr(0,s.top().size())==s.top())
return true;
else
return false;
}int main(int argc, char const *argv[])
{
cin>>n;
for (int i = 0; i < n; ++i)
{
string t;
cin>>t;
while(!is_ok(t))
s.pop();
s.push(t);
if (s.size()>ans)
ans=s.size();
}
cout<<ans;
return 0;
}
```-
· @ 6 年前
-
-
0
#include<iostream>
#include <algorithm>
using namespace std;
#include<string>
string Arr[2005];
int main()
{
int n;
int max = 1;
int sum = 1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> Arr[i];
}
sort(Arr, Arr + n);for (int i = 1; i < n; i++)
{
sum = 1;
for (int j = 0; j < i; j++)
{
if (Arr[i].compare(0, Arr[j].length(), Arr[j], 0, Arr[j].length()) == 0)
{
sum += 1;
}
}
if (max < sum)
max = sum;
}
cout << max<< endl;
} -
0
#include<iostream>
#include <algorithm>
using namespace std;
#include<string>
string Arr[2005];
int main()
{
int n;
int max = 1;
int sum = 1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> Arr[i];
}
sort(Arr, Arr + n);for (int i = 1; i < n; i++)
{
sum = 1;
for (int j = 0; j < i; j++)
{
if (Arr[i].compare(0, Arr[j].length(), Arr[j], 0, Arr[j].length()) == 0)
{
sum += 1;
}
}
if (max < sum)
max = sum;
}
cout << max<< endl;
} -
0
#include<iostream>
#include <algorithm>
using namespace std;
#include<string>
string Arr[2005];
int main()
{
int n;
int max = 1;
int sum = 1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> Arr[i];
}
sort(Arr, Arr + n);for (int i = 1; i < n; i++)
{
sum = 1;
for (int j = 0; j < i; j++)
{
if (Arr[i].compare(0, Arr[j].length(), Arr[j], 0, Arr[j].length()) == 0)
{
sum += 1;
}
}
if (max < sum)
max = sum;
}
cout << max<< endl;
}//俺也不知道你们为啥那么复杂 -
0
1156400231 LV 7 @ 7 年前
var
a:array [1..2000] of string;
b:array [1..2000] of longint;
i,j,k,n,m,s,t:longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
begin
readln(n);
for i:=1 to n do
readln(a[i]);
for i:=1 to n do
b[i]:=1;
for i:=1 to n do
for j:=i+1 to n do
if copy(a[j],1,length(a[i]))=a[i] then b[j]:=max(b[j],b[i]+1);
s:=0;
for i:=1 to n do
if b[i]>s then s:=b[i];
write(s);
end. -
0
program543 LV 8 @ 7 年前
数据有点水，随便写了一个就过了
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
struct node
{
char data[76];
};
node s[2001];
int f[2001];
bool in_it(node a,node b)
{
if (strlen(a.data)>strlen(b.data)) return false;
for (int k=0;k<=strlen(a.data)-1;k++)
if (a.data[k]!=b.data[k])
return false;
return true;
}
int main()
{scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%s",s[i].data);
}
for (int i=1;i<=n;i++)
f[i]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<i;j++)
if (in_it(s[j],s[i]))
f[i]=max(f[i],f[j]+1);
int maxn=f[1];
for (int i=2;i<=n;i++)
maxn=max(maxn,f[i]);
printf("%d\n",maxn);
return 0;
} -
0
trie树查找，为什么第一眼就是trie。。。
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300000;
struct Tree {
int child[65],bj;
void clear() {
memset(child,0,sizeof(child));
bj=0;
}
};
struct Trie {
Tree tree[maxn];
int cnt;
void init() {
cnt=0;
memset(tree,0,sizeof(tree));
}
void insert(string s) { //插入字符串s
int x=0;
for(int i=0; i<s.length(); i++) {
int y=s[i]-'a';
if(tree[x].child[y]==0) { //没有此结点，新建结点
tree[x].child[y]=++cnt;
tree[cnt].clear();
x=cnt;
} else x=tree[x].child[y];
}
tree[x].bj=1;
}
int Find(string s) {
int x=0,sum=0;
for(int i=0; i<s.length(); i++) {
int y=s[i]-'a';
if(tree[x].child[y]==0)return -1; //不在树中
x=tree[x].child[y];
sum+=tree[x].bj;
}
return sum;
}
};
Trie trie;
int n,ans=0;
string s[2005];
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++) {
cin>>s[i];
trie.insert(s[i]);
}
for(int i=1; i<=n; i++)ans=max(ans,trie.Find(s[i]));
printf("%d\n",ans);
return 0;
}-------华丽的昏割线-------
的确也可以用c++库函数LIS做，但是用的string速度要慢很多
-------华丽的昏割线-------#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,ans=0;
string s[2005];
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++)cin>>s[i];
for(int i=1; i<=n; i++) {
int sum=0;
for(int j=1; j<=i; j++)
if(s[i].find(s[j])==0)sum++;
ans=max(ans,sum);
}
printf("%d\n",ans);
return 0;
} -
0
最长上升子序列题目吧
var
a:array[1..2000] of string;
l:array[1..2000] of integer;
i,j,n,max:integer;
function maxn(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;begin
readln(n);
for i:=1 to n do
begin
l[i]:=1;
readln(a[i]);
end;
for i:=2 to n do
for j:=1 to i-1 do
if pos(a[j],a[i])=1 then
l[i]:=maxn(l[i],l[j]+1);
max:=0;
for i:=1 to n do
if l[i]>max then max:=l[i];
writeln(l[i]);
end. -
0
/最后一个点是猴子派来的吗
#include <iostream>
#include <string>using namespace std;
#define MAXS 2001
int n;
string word[MAXS];
int f[MAXS];int main()
{
int i,j;
string te;
int t;
cin>>n;
for(i=0;i<=n;++i)
f[i]=1;
for(i=1;i<=n;++i)
cin>>word[i];
//f[n]=1;
for(i=n-1;i>0;--i)
{
t=word[i].size();
for(j=n;j>i;--j)
{
if(word[i][0]!=word[j][0])continue;
te=word[j].substr(0,t);
if(te==word[i])
f[i]=max(f[i],f[j]+1);
}
}
j=-1;
for(i=0;i<=n;++i)
j=max(j,f[i]);
cout<<j;
return 0;
} -
0
TRIE树dp什么乱七八糟的。。貌似是trie树上的最长单词链单词数。。。啊一次A。。Orz
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>using namespace std;
int n,num=1;
char in[1000];struct T{
int tot,ch[300];
}t[10000];int insert(char s,int &x){
!x&&(x=++num);
if((s+1)=='\0')return t[x].tot=1;
insert(s+1,t[x].ch[*(s+1)]);
}int dfs(int x,int ret=0){
for(register int i=0;i<300;i++)t[x].ch[i]&&(ret=max(ret,dfs(t[x].ch[i])));
return ret+(t[x].tot==1);
}int main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++){
scanf("%s",in);
insert(in,t[1].ch[*in]);
}printf("%d\n",dfs(1));
}
larryzhong
LV 9
@ 7 年前
信息
- ID
- 1028
- 难度
- 4
- 分类
- 动态规划 | LIS 点击显示
- 标签
- (无)
- 递交数
- 6024
- 已通过
- 2446
- 通过率
- 41%
- 被复制
- 9
- 上传者
-
Vivian Snow
