首页 > 代码库 > CodeForces 358D — Dima and Hares

CodeForces 358D — Dima and Hares

这题要备忘一下,对于简单的偏序关系对应的价值也可以施行dp。

 

/*ID:esxgx1LANG:C++PROG:cf358D*/#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 3007;unsigned joy[maxn][3];unsigned dp[2][2];int main(void){    #ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);    #endif    int N;    scanf("%d", &N);    for(int i=0; i<N; ++i) scanf("%u", &joy[i][0]);    for(int i=0; i<N; ++i) scanf("%u", &joy[i][1]);    for(int i=0; i<N; ++i) scanf("%u", &joy[i][2]);        int curr = 0;    dp[0][0] = joy[0][0], dp[0][1] = joy[0][1];    for(int i=2; i<=N; ++i) {        // 所处位置是c, 当前要决定b, 若b<c,即 a < b < c(1), b < a < c(0), b < c < a(0)        dp[!curr][0] = max(dp[curr][0] + joy[i-1][1], dp[curr][1] + joy[i-1][0]);        // 若 c < b, 即 c < a < b, a < c < b(2),  c < b < a (1)        dp[!curr][1] = max(dp[curr][0] + joy[i-1][2], dp[curr][1] + joy[i-1][1]);        curr = !curr;    }        printf("%u\n", dp[curr][0]);    return 0;}

 

CodeForces 358D — Dima and Hares