C/C++教程

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 动态规划 状态转移方程的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!