题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4521
题意:
给出一个2*n的矩阵,取数使得到的结果最大,要求取的数不能有公共边。
代码如下:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[3][100017], dp[3][100017];int main(){int t;int n;scanf("%d",&t);while(t–){scanf("%d",&n);for(int i = 1; i <= 2; i++){for(int j = 1; j <= n; j++){scanf("%d",&a[i][j]);}}memset(dp,0,sizeof(dp));dp[1][1] = a[1][1];dp[2][1] = a[2][1];for(int j = 2; j <= n; j++){dp[1][j] = max(dp[2][j-1],dp[2][j-2])+a[1][j];dp[2][j] = max(dp[1][j-1],dp[1][j-2])+a[2][j];}printf("%d\n",max(dp[1][n],dp[2][n]));}return 0;}
,游手好闲会使人心智生锈