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

当前位置 : 首页 > 网页制作 > CSS > rnqoj-49-加分二叉树-(区域动归+记忆化)

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

来源: 作者: 时间:2016-01-28 09:27
区域动归的问题 includestdio h includestring h includeiostream includealgorithm using namespace std; int n; int a[51]; int vis[51][51]; int num[51][51];
区域动归的问题
 
#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 (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;  
    }  
}  

 

 
Tag:
网友评论

<