Jerry准备偷吃Tom的奶酪。所有的奶酪排成了一条直线，每块奶酪都有不同的美味程度。然而，如果有相邻两块奶酪都被Jerry偷吃，Tom就会发现这一点并迅速抓住Jerry。Jerry当然希望在不被Tom发现的条件下吃到的奶酪美味度总和最大。当然，他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案，告诉他最多能偷吃到多少的美味度吧。
2 4 1 2 3 1 5 2 7 9 3 1
4 12
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 long long d[100005]; 6 int a[100005]; 7 int main(){ 8 int t; 9 cin>>t; 10 while(t--){ 11 int n; 12 memset(d,0,sizeof(d)); 13 memset(a,0,sizeof(a)); 14 cin>>n; 15 for(int i = 1; i <= n; i++) 16 cin>>a[i]; 17 d[1] = max(0, a[1]); 18 d[2] = max(int(d[1]), a[2]); 19 for(int i = 3; i <= n; i++){ 20 d[i] = max(d[i-1], a[i]+d[i-2]); 21 } 22 cout<<d[n]<<endl; 23 } 24 return 0; 25 }
备注：这道题看似水，其实暗藏一个小小的坑，还是要仔细审题啊！！美味值可能为负，这种奶酪吃了不如不吃，也就是说在初始化的时候不能直接d[1]=a[1]了，而是要跟0比较一下，d[2]也是一样的道理。
原文：https://www.cnblogs.com/fangziyuan/p/13161808.html