CodeForces - 255C——dp子序列

ゝ一纸荒年。 2022-06-13 00:59 160阅读 0赞

Think:  
1题意描述：输入一个序列，寻找一个隔位相等的最长子序列  
2状态转移方程：  
dp\[i\]\[j\] = dp\[j\]\[k\] + 1(a\[j\] == a\[k\])  
dp\[i\]\[j\]含义：以a\[i\]结尾,a\[j\]为倒数第二个的情况的最长子序列的长度  
k:在转移过程中与a\[i\]相等的比当前位小的最大的位  
3反思：  
1>dp转移方程理解不深入  
2>过度依赖别人博客，缺少自己的思考

[vjudge题目链接][vjudge]  
[建议参考博客][Link 1]

以下为Wrong Answer代码——最长子序列长度为１的情况

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 4e3 + 4;
    
    int a[N], dp[N][N];
    
    int main(){
        int n, i, j, k, ans;
        while(~scanf("%d", &n)){
            ans = 0;
            memset(dp, 0, sizeof(dp));
            for(i = 0; i < n; i++)
                scanf("%d", &a[i]);
            for(i = 0; i < n; i++){
                k = -1;
                for(j = 0; j < i; j++){
                    if(k == -1)
                        dp[i][j] = 2;
                    else
                        dp[i][j] = dp[j][k] + 1;
                    if(a[j] == a[i])
                        k = j;
                    ans = max(ans, dp[i][j]);
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 4e3 + 4;
    
    int a[N], dp[N][N];
    
    int main(){
        int n, i, j, k, ans;
        while(~scanf("%d", &n)){
            ans = 1;
            memset(dp, 0, sizeof(dp));
            for(i = 0; i < n; i++)
                scanf("%d", &a[i]);
            for(i = 0; i < n; i++){
                k = -1;
                for(j = 0; j < i; j++){
                    if(k == -1)
                        dp[i][j] = 2;
                    else
                        dp[i][j] = dp[j][k] + 1;
                    if(a[j] == a[i])
                        k = j;
                    ans = max(ans, dp[i][j]);
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/CodeForces-255C
[Link 1]: http://blog.csdn.net/qq_24451605/article/details/48659235