洛谷P1481 魔族密码(LIS)

题意

题目链接

给出一堆字符串,若一个串是另一个串的前缀 ,那么它们可以连接在一起

问最大的链接长度

Sol

LIS沙比提其实是做完了才看出是LIS

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define LL long long
// #define int long long  
using namespace std;
const int MAXN = 2001, INF = 1e9 + 7, mod = 998244353;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
string s[MAXN];
int f[MAXN];
bool suf(string a, string b) {
    int cur = 0;
    for(int i = 0; i < a.length(); i++) {
        if(a[i] != b[cur]) return 0;
        cur++;
    }
    return 1;
}
main() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> s[i];
    int ans = 0;
    for(int i = 1; i <= N; i++) {
        f[i] = 1;
        for(int j = 1; j < i; j++) {
            if(suf(s[j], s[i])) f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
    }
    printf("%d", ans);
    return 0;
}
/*
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

java虚拟机构造原理

 Java虚拟机的生命周期 一个运行中的Java虚拟机有着一个清晰的任务:执行Java程序。程序开始执行时他才运行,程序结束时他就停止。你在同一台机器上运行三...

1986
来自专栏Linux驱动

22.QT-QXmlStreamReader解析,QXmlStreamWriter写入

XML 用于存储数据,数据的形式类似于树结构(参考: http://www.runoob.com/xml/)

1355
来自专栏Java技术分享圈

Java的数据库连接工具类的编写

1234
来自专栏DOTNET

asp.net web api 异常捕获

1 向客户端发送错误消息 使用throw new HttpResponseException()向客户端抛出错误信息。 HttpResponseExceptio...

50812
来自专栏前端侠2.0

co yield避免嵌套详细代码示例。

1381
来自专栏博岩Java大讲堂

多线程--同步与锁

2243
来自专栏Java编程技术

什么是重排序与中断

Java内存模型中,允许编译器和处理器对指令进行重排序,但是重排序可以保证最终执行的结果是与程序顺序执行的结果一致,并且只会对不存在数据依赖性的指令进行重排序,...

812
来自专栏Ryan Miao

java线程(2)--同步和锁

参考转载:http://rainyear.iteye.com/blog/1734311 http://turandot.iteye.com/blog/17040...

3707
来自专栏FreeBuf

Safari信息泄露漏洞分析

Javascript中的数组和数组对象一直都是编程人员优化的主要目标,一般来说,数组只会包含一些基本类型数据,比如说32位整数或字符等等。因此,每个引擎都会对这...

892
来自专栏Java 源码分析

Bootstrap 源码分析

Netty 源码分析: Bootstrap 1. 结构 先看一个这个类的类层次结构, ? 好,这个结构还是比较明晰的,然后看他的主要字段,因为这些字段比较重...

2845

扫码关注云+社区

领取腾讯云代金券