codeforces 813 D. Two Melodies（dp）

题目链接：http://codeforces.com/contest/813/problem/D

题意：求两个不相交的子集长度之和最大是多少，能放入同一子集的条件是首先顺序不能变，然后每一个相邻的要么相差1或者相差7的倍数。

题解：应该会想到是dp，看数据量有可能是二维的不妨设dp[i][j],由于这里只需要求两组所以dp[i][j]要表示为一组以i为结尾，一组以j为结尾。那么如何更新dp?

i=j时dp[i][j]=0没什么好说的。这里可以选择一个基准遍历结尾小的，更新结尾大的。为什么要这么选？

假设x>y，如果更新dp[x][y]是从dp[x][i]来的话可能不能确保以x为结尾的最大值不经过i点。所以要更新dp[i][y]。大致思路是这样的具体看一下代码是怎么实现的。

#include <iostream>

#include <cstring>

using namespace std;

const int M = 5e3 + 10;

const int N = 1e5 + 10;

int a[M];

int maxmod[8];//a[i] mod 7 == j 时dp[i][y]的最大值

int maxnum[N];//a[i] == j 时dp[i][y]的最大值

int dp[M][M];

int main() {

    int n;

    cin >> n;

    for(int i = 1 ; i <= n ; i++) cin >> a[i];

    memset(dp , 0 , sizeof(dp));

    int ans = 0;

    for(int i = 0 ; i <= n ; i++) {

        memset(maxmod , 0 , sizeof(maxmod));

        memset(maxnum , 0 , sizeof(maxnum));

        for(int j = 1 ; j <= i ; j++) {

            maxmod[a[j] % 7] = max(maxmod[a[j] % 7] , dp[i][j]);

            maxnum[a[j]] = max(maxnum[a[j]] , dp[i][j]);

        }

        for(int j = i + 1 ; j <= n ; j++) {

            dp[i][j] = max(dp[i][0] + 1 , dp[i][j]);

            dp[i][j] = max(maxmod[a[j] % 7] + 1 , dp[i][j]);

            dp[i][j] = max(maxnum[a[j] + 1] + 1 , dp[i][j]);

            dp[i][j] = max(maxnum[a[j] - 1] + 1 , dp[i][j]);

            maxmod[a[j] % 7] = max(maxmod[a[j] % 7] , dp[i][j]);

            maxnum[a[j]] = max(maxnum[a[j] + 1] , dp[i][j]);

            dp[j][i] = dp[i][j];

            ans = max(ans , dp[i][j]);

        }

    }

    cout << ans << endl;

    return 0;

}

巴特西

codeforces 813 D. Two Melodies（dp）

最新文章

热门文章