暴搜-->记忆化-->DP
P2858 [USACO06FEB]奶牛零食Treats for the Cows
题解
区间DP？？？我咋没看出来
当你不会的时候，就开始暴搜吧
每次可以取得区间左端点卖出或者区间右端点卖出
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<queue> using namespace std; typedef long long ll; inline int read() { int ans=0; char last=' ',ch=getchar(); while(ch<'0'||ch>'9') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int n; int v[2005]; ll ans=0; void dfs(int k,int l,int r,ll sum) { if(k>n) {ans=max(ans,sum); return ;} dfs(k+1,l+1,r,sum+v[l]*k); dfs(k+1,l,r-1,sum+v[r]*k); } int main() { n=read(); for(int i=1;i<=n;i++) v[i]=read(); dfs(1,1,n,0); printf("%lld ",ans); return 0; }
考虑一下记忆化
dp[L][R] 表示卖出零食 L~R 的最大花费
（然后AC了）
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<queue> using namespace std; inline int read() { int ans=0; char last=' ',ch=getchar(); while(ch<'0'||ch>'9') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int n,v[2005],ans=0; int dp[2005][2005]; int dfs(int k,int l,int r) { if(l>r) return 0; if(dp[l][r]!=0) return dp[l][r]; if(l==r) return v[l]*k; dp[l][r]=max(dfs(k+1,l+1,r)+v[l]*k,dfs(k+1,l,r-1)+v[r]*k); return dp[l][r]; } int main() { n=read(); for(int i=1;i<=n;i++) v[i]=read(); dp[1][n]=dfs(1,1,n); printf("%d ",dp[1][n]); return 0; }
然后发现貌似找到了递推式子
既然是区间DP那就考虑最外层枚举区间长，下一层枚举左端点，手动计算右端点
问题来了：k 怎么求？？
比如需要计算区间 [ 3,5 ]
1 2 [ 3 4 5 ] 6
那么它外面的就都已经卖出去了
一共卖出了：（L - 1) + (n - R）个，那么现在再卖一个，就是第 （n - R + L）个
由于 R=L+len-1
所以 k = n - len + 1
初始化：dp[ i ][ i ] 区间内只有一个元素，也就说明这个元素是最后一个被卖出的
代码
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<queue> using namespace std; inline int read() { int ans=0; char last=' ',ch=getchar(); while(ch<'0'||ch>'9') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int n,v[2005],ans=0; int dp[2005][2005]; int main() { n=read(); for(int i=1;i<=n;i++) v[i]=read(); for(int i=1;i<=n;i++) dp[i][i]=v[i]*n; for(int l=2;l<=n;l++) for(int i=1;i+l-1<=n;i++) { int j=i+l-1; dp[i][j]=max(dp[i+1][j]+v[i]*(n-l+1),dp[i][j-1]+v[j]*(n-l+1)); } printf("%d ",dp[1][n]); return 0; }