?

題目傳送門

/*題意：兩行數字，相鄰列一上一下，或者隔一列兩行都可以，從左到右選擇數字使和最大DP：狀態轉移方程：dp[i][j] = max (dp[i][j], dp[1-i][j-1] + a[i][j], dp[i/1-i][j-2] + a[i][j]);要從前面一個轉態推過來啊，我比賽寫反了，內功不夠:(
*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cstdlib>
using namespace std;const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[2][MAXN];
int dp[2][MAXN];int main(void)        //UVALive 6506 Padovan Sequence
{
//    freopen ("K.in", "r", stdin);int t;    scanf ("%d", &t);while (t--){int n;    scanf ("%d", &n);memset (dp, 0, sizeof (dp));for (int i=0; i<=1; ++i){for (int j=1; j<=n; ++j){scanf ("%d", &a[i][j]);}}dp[0][1] = a[0][1];    dp[1][1] = a[1][1];int ans = max (dp[0][1], dp[1][1]);for (int j=2; j<=n; ++j){for (int i=0; i<=1; ++i){dp[i][j] = max (dp[i][j], dp[1-i][j-1] + a[i][j]);if (j > 2){dp[i][j] = max (dp[i][j], dp[i][j-2] + a[i][j]);dp[i][j] = max (dp[i][j], dp[1-i][j-2] + a[i][j]);}ans = max (ans, dp[i][j]);}}printf ("%d\n", ans);}return 0;
}

?

轉載于:https://www.cnblogs.com/Running-Time/p/4592491.html

總結

以上是生活随笔為你收集整理的DP UVALive 6506 Padovan Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。