CodeForces - 255C——dp子序列-蒲公英云

CodeForces - 255C——dp子序列

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题目链接
建议参考博客

以下为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;
}