首页 > 代码库 > 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;}
Accepted | 44 KB | 31 ms | GNU C++ 4.6 | 951 | 2014-10-21 12:41:53 |
CodeForces 358D — Dima and Hares
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。