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
",dfs(1,n));
    }
    return 0;
}