关于这道题, 我有个很大的疑问.
我们可以记录头和尾再加一个卖了的零食数目, 如果头超过尾就 return 0.
如果遇到需要重复使用的数,(也就是不为零的 d 数组) 就直接 return d[tuo][wei].
如果没有, 就取卖头一个与最后一个的最大值, 并记录下来.
代码也有注释, 具体可以自己看.
- #include<bits/stdc++.h>
- using namespace std;
- int n,a[2001],d[2001][2001];
- int dfs(int gong,int tuo,int wei)
- {
- if(tuo>wei)
- {
- return 0;// 返回
- }
- if(d[tuo][wei])
- {
- return d[tuo][wei];// 运用记忆化
- }
- return d[tuo][wei]=max(dfs(gong+1,tuo+1,wei)+gong*a[tuo],dfs(gong+1,tuo,wei-1)+gong*a[wei]);// 运用记忆化
- }
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- }
- cout<<dfs(1,1,n)<<endl;// 输出
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3156995.html