放假回来了，在家咸鱼了一周.........不会区间dp，今天下午做个区间dp专题试试
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=100+10; int a[maxn],sum[maxn],dp[maxn][maxn]; bool vis[maxn][maxn]; int n; const int inf=-0x3f3f3f3f; int d(int l,int r) { if(l>r) return 0; if(vis[l][r]) return dp[l][r]; vis[l][r]=1; int mm=inf,sum1=0,sum2=0; for(int i=l; i<=r; i++) { sum1+=a[i]; mm=max(mm,sum1-d(i+1,r));//寻找差值最大 } for(int i=r; i>=l; i--) { sum2+=a[i]; mm=max(mm,sum2-d(l,i-1)); } return dp[l][r]=mm; } int main() { while(~scanf("%d",&n)&&n) { memset(sum,0,sizeof(sum)); memset(vis,0,sizeof(vis)); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } printf("%d\n",d(1,n)); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7357505.html
