Codeforce 1195C 动态规划 状态转移方程

本文主要是介绍Codeforce 1195C 动态规划 状态转移方程，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接：http://codeforces.com/problemset/problem/1195/C

题意：给出两行数字（个数相同），每两个数字不能上下或左右相邻，计算出所有数字满足条件的最大和。

思路：利用dp数组存储到达每一个位置的最大值，方法的核心在于选或不选。根据经典的背包问题，选则总价值增加，当前容量减少，不选则保留当前数值不变。回归本题，选则当前值加另一行积累的dp数值，不选则保持本行已积累数值不变。最终两行分别得出所积累的dp数值，选较大的一个输出。总而言之，每一行对应一个数组，记录当前和的最大值。

for(int i=1;i<=n;i++){
    dp[0][i]=max(a[i]+dp[1][i-1],dp[0][i-1]);
    dp[1][i]=max(b[i]+dp[0][i-1],dp[1][i-1])；
}

细节：i从1开始，第一次循环用到(i-1)时i即为0，不会有乱七八糟的数据被计算；遍历某一行时，若选择选用本行的数值，相加时引用的是另一行的数据，所以不会发生因遍历而使得数值相邻的情况。

完整代码：

#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000010

typedef long long ll;
ll a[N],b[N],dp[3][N];
int main(int argc, char** argv) {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=n;i++){
        dp[0][i]=max(a[i]+dp[1][i-1],dp[0][i-1]);
        dp[1][i]=max(b[i]+dp[0][i-1],dp[1][i-1]);
    }
    printf("%lld\n",max(dp[0][n],dp[1][n]));
    return 0;
}

这篇关于Codeforce 1195C 动态规划 状态转移方程的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！