rnqoj-49-加分二叉树-（区域动归+记忆化）

区域动归的问题
 

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
int n;  
int a[51];  
int vis[51][51];  
int num[51][51];  
int dll(int l,int r)  
{  
    int i;  
    if(num[l][r]!=-1)return num[l][r];  
    if(l>r)  
    {  
        return 1;  
    }  
    if(l==r)  
    {  
        num[l][r]=a[l];  
        vis[l][r]=l;  
        return a[l];  
    }  
    int as=0;  
    for(i=l;i<=r;i++)  
    {  
        int t=0;  
        t=dll(l,i-1)*dll(i+1,r)+a[i];  
        if(as<t)  
        {  
            vis[l][r]=i;  
            as=t;  
        }  
    }  
    num[l][r]=as;  
    return as;  
}  
int leap;  
void dos(int l,int r)  
{  
    if(vis[l][r]==-1)return ;  
    if(leap==0)  
    {  
        printf("%d",vis[l][r]);  
    }  
    else  
    {  
        printf(" %d",vis[l][r]);  
    }  
    leap++;  
    if(l<r)  
    {  
        dos(l,vis[l][r]-1);  
        dos(vis[l][r]+1,r);  
    }  
}  
int main()  
{  
    int i;  
    while(~scanf("%d",&n))  
    {  
        memset(num,-1,sizeof(num));  
        memset(vis,-1,sizeof(vis));  
        for(i=1;i<=n;i++)scanf("%d",&a[i]);  
        if(dll(1,n));  
        cout<<num[1][n]<<endl;  
        leap=0;  
        dos(1,n);  
        cout<<endl;  
    }  
}