一开始以为卡STL...

写dfs最后一个点被卡 想着是不是卡了.find
然后仔细想了想,我们可以把dfs改dp的,这样就在O(N^2)的时间里能出答案..

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 2000 + 10;

int n, ans;
int dp[MAXN]; 
string s[MAXN];

bool check(int i, int j) {
    if(s[j].find(s[i]) == 0) return true;
    return false;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) 
        cin >> s[i];
    for(int i = 1; i <= n; ++i) {
        if(!dp[i]) dp[i] = 1;
        for(int j = i + 1; j <= n; ++j)
            if(check(i, j)) 
                dp[j] = max(dp[j], dp[i] + 1);
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
} 

1 条评论

  • @ 2016-08-31 17:08:29

    顺便附之前写的dfs...

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    const int MAXN = 2000 + 10;
    
    int n, ans;
    int dp[MAXN];
    string s[MAXN];
    
    inline bool check(int i, int j) {
        if(i == 0) return true;
        if(s[j].find(s[i]) == 0) return true;
        return false;
    }
    
    int dfs(int i, int dep) {
        ans = max(ans, dep);
        for(int j = i + 1; j <= n; ++j) {
            if(check(i, j)) 
                dfs(j, dep + 1);
        }
        return 0;
    }
    
    int main() {
        scanf("%d", &n);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i) 
            cin >> s[i];
        dfs(0, 0);
        printf("%d\n", ans);
        return 0;
    }
    
  • 1

信息

ID
1028
难度
4
分类
动态规划 | LIS 点击显示
标签
(无)
递交数
5999
已通过
2433
通过率
41%
被复制
8
上传者