题解 P2858 【[USACO06FEB]奶牛零食Treats for the Cows】

## c++ 本次题解已经过修改，加上了代码注释。 其实我觉得USACO挺不错的，就是有的时候这个翻译什么的有点不懂。。。（其实是我看不懂。。） 这道题我一开始以为可以用贪心（两端只取最小的，把大的留到后面）做，后来发现用贪心是不行的，比如这个数据 6 1 1 5 5 1 就不行了，如果用贪心答案是71，而正确答案是75。 好吧，言归正传。 这道题的正解应该是**区间dp**，然而我是用**记忆化搜索**做的。 对于一个区间【l，r】（即l到r的位置），会存在一个最优解（最大值）。而在普通的搜索中，这个区间中的最大值会重复搜索计算，所以在这个时候我们就需要用记忆化，把最大值记录下来，避免下次重复搜索。 具体AC代码如下 ```cpp #include<stdio.h> #include<iostream> using namespace std; int n,a[2005],f[2005][2005],ans; //其中f数组表示在l,r区间中的最大值，a数组为读入//的数组，ans用来存储最后值（不用也行） int dfs(int k,int l,int r)//记忆化开始 //k代表已经卖掉了几个零食（也可表示为层次） { int p=0; if (k>n) return 0;//边界 if (f[l][r]!=-1) return f[l][r]; //如果已经搜索过，则不需要再次搜索，return if (l>r) return 0;//边界 p=max(p,dfs(k+1,l+1,r)+a[l]*k);//计算 p=max(p,dfs(k+1,l,r-1)+a[r]*k);//计算 f[l][r]=p;//存储当前最优解 return p; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) f[i][j]=-1; //赋初值标记是否搜索过 for (int i=1;i<=n;i++) { scanf("%d",&a[i]); } ans=dfs(1,1,n);//记忆化 printf("%d",ans); } 如有错误，还请指出 ```