hdu4960 区间dp

由于可以预处理出每个左端点对应的右端点，所以并不需要开二维，复杂度应该是介于n和n^2之间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;int n;
ll a[5010];
int cost[5010];
int dp[5010];
ll ls[5010],rs[5010];int Find(int x)
{int l=0,r=n+1;while(l<=r){int m=(l+r)>>1;if(rs[m]==ls[x]) return m;if(rs[m]<ls[x]) r=m-1;else l=m+1;}return -1;
}
int F[5010];int dfs(int l,int r)
{int &res=dp[l];if(~res) return res;if(l>r) return res=0;res=cost[r-l+1];int k2;REP(k,l,r-1){k2=F[k];if(k2==-1||k>=k2) continue;res=min(res,cost[k-l+1]+cost[r-k2+1]+dfs(k+1,k2-1));}return res;
}int main()
{//freopen("in.txt","r",stdin);while(~scanf("%d",&n)&&n){REP(i,1,n) scanf("%I64d",&a[i]);a[0]=a[n+1]=0;REP(i,1,n) scanf("%d",&cost[i]);ls[0]=0;REP(i,1,n) ls[i]=ls[i-1]+a[i];rs[n+1]=0;for(int i=n;i>=1;i--) rs[i]=rs[i+1]+a[i];REP(i,1,n) F[i]=Find(i);memset(dp,-1,sizeof(dp));printf("%d\n",dfs(1,n));}return 0;
}