做题感悟:其实有些题看着不好搞,但是只要你狠下心,有那种不搞定它不罢休的精神,那什么题也不算题了,自己完全搞定和百度看题解完全不一样的感觉。
解题思路:开始我把所有和都存下来,每一个点都从前往后找最优值,很明显超时。
动态方程:dp[ i ] = max( dp[ i -1 ] ,dp[ i - 2 ] + t ) ( t 是输入的第 i 个数)。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<queue> #include<algorithm> using namespace std ; const int MX = 200005 ; int b[MX],g[MX] ; int max(int x,int y) { return x > y ? x : y ; } int main() { int n,m ; while(~scanf("%d%d",&n,&m)) { memset(g,0,sizeof(g)) ; memset(b,0,sizeof(b)) ; int x ; for(int i=1 ;i<=n ;i++) { scanf("%d",&g[1]) ; for(int j=2 ;j<=m ;j++) { scanf("%d",&x) ; g[j]=max(g[j-1],g[j-2]+x) ; } b[i]=g[m] ; } for(int i=1 ;i<=n ;i++) b[i]=max(b[i-1],b[i-2]+b[i]) ; printf("%d\n",b[n]) ; } return 0 ; }