区间dp(1) P2858 [USACO06FEB]奶牛零食Treats for the Cows

胡乱分析

一道区间dp的题目，大佬的算法是既然要选择左边一个或者右边的一个，那么我们可以得到一个转移方程
dp[i][j]=max(dp[i+1][j],dp[i][j-1])+cha[j]-cha[i-1]
其中i,j是从i到j的最321优解显然答案就是dp[1][n]

代码

#include <bits/stdc++.h>
using namespace std;
int dp[2005][2005],num[2005],cha[2005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  cin>>num[i],cha[i]=cha[i-1]+num[i];
  for(int i=1;i<=n;i++)
  for(int j=1;j<=i;j++)
  dp[j][i]=max(dp[j-1][i],dp[j][i+1])+cha[i]-cha[j-1];
  cout<<dp[1][n];
}