题解

139 条题解

  • 11
    @ 2017-05-08 07:53:42
    /*
    一道披着树形dp的区间dp666666
    我们可以用记忆化递归搜索来动态规划一下
    我们知道因为该二叉树的中序遍历为1....n
    根节点的选取其实有无数种情况
    那我们就递归枚举所有可能的根节点比较所能得到的最大值
    我们设f[i][j]表示i结点到j结点的加分二叉树所能达到的最大加分值
    root[i][j]=k表示该最大加分值是在根节点为k的时候达到的
    那么我们就可以得到下面的状态转移方程
    f[i][j]=max(f[i][k-1]*f[k+1][j]+d[k],i<=k<=j)
    注意边界子树为空时加分值为1
    那么我们就记忆化搜索一下就好了
    再来考虑一下输出,要输出前序遍历
    那么我们想一下怎么输出前序遍历?
    对于f[1][n]找到其最优解的时候的根节点root[1][n]
    然后再根据这个根节点将树分成二叉树,然后再递归找到根节点输出
    边界是子树为空的时候~
    问题就解决了
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int n;
    int a[31];
    int f[31][31];
    int root[31][31];
    
    int dfs(int l,int r)
    {
        int ans=-1;
        int node=-1;
        if(f[l][r]!=-1)
            return f[l][r];
        else    if(l>r)
            return f[l][r]=1;
        else    if(l==r)
        {
            root[l][r]=l;
            return f[l][r]=a[l];
        }
        else
        {
            for(int i=l;i<=r;i++)
            {
                int temp=dfs(l,i-1)*dfs(i+1,r)+a[i];
                if(ans<temp)
                {
                    ans=temp;
                    node=i;
                }
            }
        }
        root[l][r]=node;
        return f[l][r]=ans;
    }
    
    void print(int l,int r)
    {
        if(l<=r)
        {
            cout<<root[l][r]<<" ";
            print(l,root[l][r]-1);
            print(root[l][r]+1,r);
        }
    }
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        memset(f,-1,sizeof(f));
        memset(root,-1,sizeof(root));
        dfs(1,n);
        cout<<f[1][n]<<endl;
        print(1,n);
        return 0;
    }
         
    
  • 7
    @ 2017-01-14 22:05:50

    【美妙的区间DP与树的遍历的入门】

    #include<stdio.h>
    #include<iostream>
    #define go(i,a,b) for(int i=a;i<=b;i++) 
    #define ro(i,a,b) for(int i=a;i>=b;i--)
    using namespace std;
    int f[35][35],d[35][35],ans[35],t,a[35],n;
    void P(int l, int r){
         if(l>r)return;if(l==r){ans[++t]=l;return;}
         ans[++t]=d[l][r];P(l,d[l][r]-1);P(d[l][r]+1,r);}
    int main(){
         scanf("%d",&n);
         go(i,1,n)scanf("%d",&a[i]),
         f[i][i-1]=1,f[i][i]=a[i];
         go(l,2,n)go(i,1,n){
         int j=i+l-1;go(k,i,i+l-1){
         int tmp=f[i][k-1]*f[k+1][j] + a[k];
         if (f[i][j]<tmp)f[i][j]=tmp,d[i][j]=k;}}
         
         printf("%d\n",f[1][n]);P(1,n);
         go(i,1,t)printf("%d ",ans[i]);
         printf("\n");
     }
    

    -Paul_Guderian

  • 2
    @ 2017-10-16 10:37:23
    /*
    进行区间dp,计算每一个区间树的最大值。在区间内枚举根的位置,计算最大值,用f保存,根用r保存。
    最后是树的先序遍历。 
    */
    #include<cstdio>
    int f[33][33],r[33][33],a[33],n;
    void write(int p,int q)              //先序遍历。 
    {
        if (p>q||p<1||q>n) return;       //空树,退出。 
        printf("%d ",r[p][q]);           //挖根节点。 
        write(p,r[p][q]-1);              //遍历左子。 
        write(r[p][q]+1,q);              //遍历右子。 
        return;
    }
    int main()
    {
        int i,j,k,t,s;
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            f[i][i]=a[i]; r[i][i]=i;     //只有根。 
            f[i][i-1]=1;                 //空树,置为1。 
        }
        f[n+1][n]=1;                     //同上,dp时会取到这些值。 
        for (i=1;i<n;i++)                //区间大小从(i+1)到n。 
            for (j=1;j<=n-i;j++)         //起始位置。 
                for (k=j;k<=j+i;k++)     //根。 
                {
                    t=a[k]+f[j][k-1]*f[k+1][j+i];
                    if (t>f[j][j+i]) {f[j][j+i]=t; r[j][j+i]=k;}
                }
        printf("%d\n",f[1][n]);
        write(1,n);
        return 0;
    }
    
  • 2
    @ 2017-09-01 09:37:42

    一道区间DP,代码还算短吧。

    状态:F[l][r] 表示以(l, r)为内部节点的子树取得最大值的最优解情况,转移只需枚举子树的根就行。
    方程:F[l][r] = F[l][i-1] * F[i+1][r] + Ai
    特殊的,当l > r时, F[l][r] = 1 (空树)
    特殊的,当l = r时,F[l][r] = Al

    提示:1.为什么一道树形DP的转移最后变成了区间DP的形式,这主要依赖于中序遍历的性质,及结构一定为左根右,形成了一个可递归的形式。
    2.输出的方式很明显遵循了根左右,这体现的是先序遍历的性质。

    #include <cstdio>
    #include <iostream>
    using namespace std;
    int N;
    int A[35];
    int F[35][35], R[35][35];
    int DP (int l, int r) {
        
        if (r<l) return 1;
        if (F[l][r]) return F[l][r];
        for(int i=l; i<=r; i++) {
            int val=DP(l, i-1)*DP(i+1, r)+A[i];
            if (l==r) val=A[i];
            if (val>F[l][r]) {
                R[l][r]=i;
                F[l][r]=val;
            } 
        }
        return F[l][r];
         
    }
    void PT (int l, int r) {
        
        if (l<=r) {
            int pot=R[l][r];
            cout << pot << " ";
            if (l!=r) {
                PT(l, pot-1);
                PT(pot+1 ,r);
            }
        }
        
    }
    int main () {
        
        cin >> N;
        for( int i=1; i<=N; i++)
            scanf("%d", &A[i]);
        DP(1, N); 
        cout << F[1][N] << endl;    
        PT(1, N);
        return 0;    
        
    }
    
  • 1
    @ 2017-10-18 10:21:27

    interesting

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #define max_n 55
    using namespace std;
    int n,w[max_n],j,dp[max_n][max_n],root[max_n][max_n];
    inline void print(int l,int r)
    {
        if(l>r) return ;
        printf("%d ",root[l][r]);
        print(l,root[l][r]-1);
        print(root[l][r]+1,r);
    }
    int main()
    {
        scanf("%d",&n);
        for(register int i=1;i<=n;i++) scanf("%d",&w[i]);
        for(register int l=1;l<=n;l++)
            for(register int i=1;i+l-1<=n;i++)
            {
                j=i+l-1;
                for(register int k=i;k<=j;k++)
                    if(i==j) dp[i][j]=w[i],root[i][j]=i;
                    else if(k==i) 
                    {
                        if(dp[i][j]<dp[i+1][j]+w[k])
                            dp[i][j]=dp[i+1][j]+w[k],root[i][j]=k;
                    }
                    else if(k==j) 
                    {
                        if(dp[i][j]<dp[i][j-1]+w[k])
                            dp[i][j]=dp[i][j-1]+w[k],root[i][j]=k;
                    }
                    else 
                    {
                        if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+w[k])
                            dp[i][j]=dp[i][k-1]*dp[k+1][j]+w[k],root[i][j]=k;
                    }
            }
        printf("%d\n",dp[1][n]);
        print(1,n);
        return 0;
    }
    
    
  • 1
    @ 2017-09-23 16:29:04

    #include <iostream>
    using namespace std;
    int n,a[35];
    long long f[35][35],p[35][35];
    void pre_order(int l,int r)
    {
    if(l==r)
    {
    cout<<l<<" ";
    }
    else if(l==r-1)
    {
    cout<<l<<" "<<r<<" ";
    }
    else
    {
    cout<<p[l][r]<<" ";
    pre_order(l,p[l][r]-1);
    pre_order(p[l][r]+1,r);
    }

    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {

    cin>>a[i];
    f[i][i]=a[i];
    }

    for(int k=1;k<n;k++)
    {
    for(int i=1;i<=n-k;i++)
    {

    f[i][i+k]=f[i][i]+f[i+1][i+k];
    p[i][i+k]=i;
    long long data;
    for(int j=i+1;j<i+k;j++)
    {
    data=f[i][i+k];
    f[i][i+k]=max(f[i][i+k],f[i][j-1]*f[j+1][i+k]+f[j][j]);
    if(data!=f[i][i+k])
    p[i][i+k]=j;
    }
    data=f[i][i+k];
    f[i][i+k]=max(f[i][i+k],f[i][i+k-1]+f[i+k][i+k]);
    if(data!=f[i][i+k])
    p[i][i+k]=i+k;
    }
    }
    // for(int i=1;i<=n;i++)
    // {
    // for(int j=i+1;j<=n;j++)
    // {
    // cout<<p[i][j]<<endl;
    // }
    // }
    // system("pause");
    cout<<f[1][n]<<endl;
    pre_order(1,n);
    // system("pause");
    return 0;
    }

  • 1
    @ 2017-08-09 08:54:48

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;

    int n, a[35], g[35][35];
    ll f[35][35];

    void print(int l, int r){
    if(l==r){ cout<<l<<' '; return; }
    if(l>r) return;
    int tmp=g[l][r];
    cout<<tmp<<' ';
    print(l, tmp-1);
    print(tmp+1, r);
    }

    int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i], f[i][i]=a[i];
    for(int i=1;i<=n+1;i++) f[i][i-1]=1;
    for(int i=n;i>=1;i--)
    for(int j=i+1;j<=n;j++)
    for(int k=i;k<=j;k++){
    long long tmp=f[i][k-1]*f[k+1][j]+a[k];
    if(tmp>f[i][j]){
    g[i][j]=k;
    f[i][j]=tmp;
    }
    }
    cout<<f[1][n]<<endl;
    print(1, n);
    return 0;
    }

  • 1
    @ 2017-04-12 19:55:48

    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #define go(i,a,b) for(int i = a ; i <= b ; i++)
    #define long long LL
    using namespace std;
    const int maxn = 1000 + 5;
    int n,ans,f[maxn][maxn],p[maxn][maxn],v[maxn];
    void print(int l,int r)
    {
    int pos = f[l][r];
    printf("%d ",pos);
    if(l<=pos-1) print(l,pos-1);
    if(r>=pos+1) print(pos+1,r); //输出遍历的位置
    }
    int dp(int l,int r)
    {
    if(l > r) return 1;
    if(p[l][r] != -1) return p[l][r];
    if(l == r) {
    f[l][r] = l;
    return v[l];
    }int& ans = p[l][r] ; int& pos = f[l][r];
    for(int i = l ; i <= r ; i++)

    if(dp(l,i-1)*dp(i+1,r)+v[i]>ans)
    {
    ans=dp(l,i-1)*dp(i+1,r)+v[i];
    pos=i;
    }
    return ans;
    }
    int main()
    {
    memset(p,-1,sizeof(p));
    scanf("%d",&n);
    go(i,1,n) scanf("%d",&v[i]);
    cout<<dp(1,n)<<endl;
    print(1,n);
    return 0;
    }

  • 0
    @ 2018-10-06 14:21:17

    令\(dp[l][r]\)为\([l,r)\)区间所构成的二叉树中权值最大的权值

    则: \(dp[l][r] = \max_{m\in [l,r)} \{ dp[l][m]\cdot dp[m+1][r] + a[m] \}\)

    对每次计算维护其最优分割\(m\)即可构造前序遍历。

    import qualified Data.Map as M
    import qualified Data.Array as A
    
    maximize (x:[]) = (x,0)
    maximize (x:xs)  =
        let (x1,i) = maximize xs
        in if x<x1 then (x1,i+1) else (x,0)
    
    -- @param s 以前搜索过的状态的集合
    -- @param m 对一个(Int,Int)构成区间的子树,其最高分值
    -- @param p 对一个(Int,Int)构成区间的子树,其根
    -- @param a 每个中序遍历到的节点的权值
    -- @param x 需要查找的区间
    -- @return 查找完成区间后新的搜索过的状态的集合
    dp :: (M.Map (Int,Int) Int,M.Map (Int,Int) Int) -> 
        A.Array Int Int -> (Int,Int) -> 
        (M.Map (Int,Int) Int,M.Map (Int,Int) Int)
    dp s@(m,p) a x@(l,r)
        | x `M.member` m = (m,p)
        | l == r     = (M.insert x 1 m,p)
        | l == r-1   = (M.insert x (a A.! l) m,M.insert x l p)
        | otherwise  = 
            let plst = [l..r-1]
                ss@(sm,sp) = foldl (\s d -> ensure (ensure s a (l,d)) a (d+1,r)) s plst
                (msm,par)  = maximize $
                    map (\d -> sm M.! (l,d) * sm M.! (d+1,r) + a A.! d) plst
                ans@(ns,np)= (M.insert x msm sm,M.insert x (par+l) sp)
            in ans
    
    predParse :: M.Map (Int,Int) Int -> (Int,Int) -> [Int]
    predParse p x@(l,r)
        | l==r   = []
        | l==r-1 = [l]
        | otherwise =
            let d = p M.! x in
            [d] ++ predParse p (l,d) ++ predParse p (d+1,r)
    
    main = do
        n <- readLn
        ln <- getLine
        let a = A.listArray(0,n-1) $ (map (read::String->Int).words) ln
        let (m,p) = dp (M.empty,M.empty) a (0,n)
        print (m M.! (0,n))
        let lst = map (+1) $ predParse p (0,n)
        putStrLn $ (unwords.map show) lst
    
  • 0
    @ 2018-08-04 09:12:43

    这题应该搞个SPJ。。
    一开始只要大于等于就更新,就WA,改成严格大于才更新就AC了

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    int n;
    int a[31];
    int root[31][31];
    int f[31][31];
    void print(int l,int r) {
        if (l>r) return;
        if (l==r) {
            cout<<l<<" ";
            return;
        }
        cout<<root[l][r]<<" ";
        print(l,root[l][r]-1);
        print(root[l][r]+1,r);
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n;
        FOR(i,n) cin>>a[i];
        FOR(i,n) f[i][i]=a[i],root[i][i]=i;
        REP(len,2,n) {
            FOR(i,n) if (i+len-1<=n) {
                int j=i+len-1;
                REP(k,i,j) {
                    int res;
                    if (k==i) {
                        res=1*f[k+1][j]+a[k];
                    } else if (k==j) {
                        res=f[i][k-1]*1+a[k];
                    } else res=f[i][k-1]*f[k+1][j]+a[k];
                    if (res>f[i][j]) {
                        f[i][j]=res;
                        root[i][j]=k;
                    }
                }
            }
        }
        cout<<f[1][n]<<endl;
        print(1,n);
        return 0;
    }
    
  • 0
    @ 2018-06-07 19:54:40

    #include<cstdio>
    #include<cstring>
    using namespace std;
    int f[31][31],root[31][31];
    int d[31];
    void pre_dfs(int l,int r)
    {
    if(l<=r)
    {
    printf(" %d",root[l][r]);
    pre_dfs( l , root[l][r]-1 );
    pre_dfs( root[l][r]+1 , r );
    }
    }

    int main()
    {
    int n;scanf("%d",&n);for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) f[i][j]=1;
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&d[i]);
    root[i][i]=i;
    f[i][i]=d[i];
    }
    for(int k=2;k<=n;k++)
    for(int L=1;L<=n-k+1;L++)
    {
    int R=L+k-1;
    for(int mid=L;mid<=R;mid++)
    {
    if( f[L][R] < f[L][mid-1] * f[mid+1][R] + d[mid])
    {
    f[L][R]= f[L][mid-1]*f[mid+1][R]+d[mid];
    root[L][R]=mid;
    }
    }
    }
    printf("%d\n",f[1][n]);printf("%d",root[1][n]);pre_dfs(1,root[1][n]-1);pre_dfs(root[1][n]+1,n);return 0;
    }
    //真的还好

  • 0
    @ 2018-01-28 21:54:10

    import java.util.Scanner;

    public class Main {
    static Scanner in = new Scanner(System.in);
    static int n;
    static int[] a = new int[35];
    static int[][] f = new int[35][35];
    static int[][] root = new int[35][35];
    public static void main(String[] args) {
    n = in.nextInt();
    for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
    f[i][j] = 1;
    }
    }
    for (int i = 1; i <= n; i++) {
    /**
    * 直接赋给f[i][i],即叶子的加分就是叶节点本身的分数
    * root[i][j]
    * /
    a[i] = in.nextInt();
    f[i][i] = a[i];
    root[i][i] = i;
    }
    /
    *
    * f[i][j] 表示区间为i-j的最大加分时的根节点
    * root[i][j] 表示区间在i-j内的父结点编号
    * k 枚举区间长度 1--(n-1)
    * i 枚举区间起点 1--(n-k)
    * i+k 代表区间终点
    * j 枚举区间中的根
    * */
    for(int k = 1; k < n; k++) {
    for(int i =1 ; i + k <= n; i++) {
    for(int j = i; j <= i + k; j++) {
    int s = f[i][j-1] * f[j+1][i+k] + f[j][j];
    if(s > f[i][i+k]) {
    f[i][i+k] = s;
    root[i][i+k] = j;
    }
    }
    }
    }

    System.out.println(f[1][n]);
    PT(1, n);
    }
    /**
    * 输出
    * */
    private static void PT(int l, int r) {
    if (l <= r) {
    System.out.print(root[l][r] + " ");
    PT(l, root[l][r] - 1);
    PT(root[l][r] + 1, r);
    }
    }
    }

  • 0
    @ 2017-10-29 19:42:58

    一道树形(*区间*)DP

    /*vijos1100 加分二叉树

    设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
    subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数
    若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
    试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;
    (1)tree的最高加分
    (2)tree的前序遍历
    By linus@chen
    at CDFLS 2017.10.29 Sun
    */

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define maxn 31
    using namespace std;

    inline int read()
    {
    char ch =getchar();int f=1,res=0;
    while(ch>'9'||ch<'0'){ if(ch == '-') f=-1;ch = getchar();}
    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+ch - '0',ch = getchar();
    return res*f;
    }

    int n,a[maxn],dp[maxn][maxn],path[maxn][maxn],p;//DP[i][j]记录i到j之间的节点的最大加分

    inline int dfs(int l,int r)
    {
    if(dp[l][r]) return dp[l][r];
    if(l > r) return 1;
    if(l == r) dp[l][r] = a[l],path[l][r] = l;
    else
    {
    for(int i=l;i<=r;i++)
    {
    int x = dfs(l,i-1) * dfs(i+1,r) + a[i];
    if(x > dp[l][r])
    dp[l][r] = x,path[l][r] = i;
    }
    }
    return dp[l][r];
    }

    inline void front(int l,int r)
    {
    if(l>r) return;
    printf( p ++ == 0 ? "%d" : " %d",path[l][r]);
    front(l,path[l][r]-1);
    front(path[l][r]+1,r);
    }

    inline void work()
    {
    n=read();
    for(int i=1;i<=n;i++) a[i] = read();
    dfs(1,n);
    printf("%d\n",dp[1][n]);
    front(1,n);
    }

    int main()
    {
    work();
    return 0;
    }

  • 0
    @ 2017-10-24 14:18:52
    using namespace std;
    const int N = 109; 
    int ans[N][N]={0};int gen[N][N]={0};
    inline void dfs(int l,int r)
    {
        if ( l > r )    return ;
        if ( l == r )
        {
            printf("%d ",l);    return ;
        }
        printf("%d ",gen[l][r]);
        dfs(l,gen[l][r]-1);dfs(gen[l][r]+1,r);
    }
    int main()
    {
        freopen("in.txt","r",stdin);
        int n; cin>>n; 
        
        for (int i = 0; i <= n+1; i++)
        for (int j = 0; j <= n+1; j++)
            ans[i][j]=1; 
            
        for (int i = 1; i <= n; i++)
            cin>>ans[i][i];
        
        for (int l = n; l >= 1; l--)
        for (int r = l+1; r <= n; r++)
        {
            int zgen=0;int maxgen=0;
            for (int k = l; k <= r; k++)
                if ( ans[l][k-1]*ans[k+1][r]+ans[k][k] > maxgen )
                {
                    zgen = k;   maxgen=ans[l][k-1]*ans[k+1][r]+ans[k][k];
                }
            ans[l][r]=maxgen;
            gen[l][r]=zgen; 
        }
        
        printf("%d\n",ans[1][n]);
        dfs(1,n);
            
        return 0;   
    
    
  • 0
    @ 2017-10-06 20:17:43

    var
    n,p,i,j,k:Longint;
    a:array[0..105] of longint;
    f,root:array[0..105,0..105] of longint;
    procedure dfs(l,r:longint);
    begin
    if l>r then exit;
    write(root[l,r],' '); dfs(l,root[l,r]-1); dfs(root[l,r]+1,r);
    end;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do begin f[i,i-1]:=1; f[i,i]:=a[i]; root[i,i]:=i; end;
    for p:=1 to n-1 do
    for i:=1 to n-p do
    begin
    j:=i+p;
    for k:=i to j do
    if f[i,j]<f[i,k-1]*f[k+1,j]+a[k] then begin f[i,j]:=f[i,k-1]*f[k+1,j]+a[k]; root[i,j]:=k; end;
    end;
    writeln(f[1,n]); dfs(1,n);
    end.

  • 0
    @ 2017-09-23 15:56:07

    #include <iostream>
    using namespace std;
    int in[50];
    int f[50][50];
    int mr[50][50];
    int dp(int s, int t)
    {
    int temp, rl, rr;
    if(s > t) return 1;
    if(s == t) return in[s];
    if(f[s][t] != 0) return f[s][t];
    for(int i = s; i <= t; ++i)
    {
    temp = f[s][t];
    f[s][t] = max(f[s][t], dp(s, i-1) * dp(i+1, t) + in[i]);
    if(f[s][t] > temp)
    mr[s][t] = i;
    }
    return f[s][t];
    }
    void output(int s, int t)
    {
    if(s == t) {cout << s << ' '; return ;}
    if(s > t) return ;
    cout << mr[s][t] << ' ';
    output(s, mr[s][t] - 1);
    output(mr[s][t] + 1, t);
    }
    int main()
    {
    int n, ans=0, r;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    cin >>in[i];

    ans = dp(1, n);
    cout << ans << endl;
    output(1, n);
    cout << endl;
    return 0;
    }

  • 0
    @ 2016-11-06 16:42:26

    //P1100加分二叉树
    #include <cstdio>
    #include <cctype>
    #include <cstring>

    const int N = 35;

    int value[N];//输入的每个节点的分数
    int n;//节点数
    int root[N][N];
    //为了输出中序遍历,存下树 root[left][right] 表示点left, left + 1, left + 2... right - 1, right得到最优解时的父节点
    int dp[N][N];
    //dp[left][right]的最高分数,此题测试数据弱,不用long long也能过

    inline int Read(){
    int rtn = 0;
    char tmp = getchar();
    while (!isdigit(tmp)) tmp = getchar();
    while (isdigit(tmp)){
    rtn = rtn * 10 + tmp - '0';
    tmp = getchar();
    }
    return rtn;
    }

    int dptree(int l, int r){
    if (dp[l][r] != -1) return dp[l][r];
    if (l > r)//树是空的
    return 1;
    if (l == r) return value[l];
    int rtn = -1;
    for (int i = l; i <= r; i++)//把所有可能出现的解都枚举一遍
    if (rtn < dptree(l, i - 1) * dptree(i + 1, r) + value[i]){
    rtn = dptree(l, i - 1) * dptree(i + 1, r) + value[i];
    root[l][r] = i;
    }
    dp[l][r] = rtn;//存下答案
    return rtn;
    }

    void midord(int l, int r){
    if (l > r) return;
    printf("%d ", root[l][r]);
    midord(l, root[l][r] - 1);
    midord(root[l][r] + 1, r);
    }

    int main(){
    memset(root, -1, sizeof(root));
    memset(dp, -1, sizeof(dp));
    n = Read();
    for (int i = 1; i <= n; i++){
    value[i] = Read();
    root[i][i] = i;
    }
    printf("%d\n", dptree(1, n));
    midord(1, n);
    putchar('\n');
    return 0;
    }

  • 0
    @ 2016-10-07 13:51:15

    #include<stdio.h> //为什么不可以用 unsigned long int 或 long
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int n,value[50],f[50][50],path[50][50];
    int search(int left,int right)
    {
    int mid,temp;
    if(f[left][right]>0)
    return f[left][right];
    if(left>right)
    {
    f[left][right]=1;
    }
    else if(left==right)
    {
    f[left][right]=value[left];
    path[left][right]=left;
    }
    else
    {
    for(mid=left;mid<=right;mid++)
    {
    temp=search(left,mid-1)* search(mid+1,right)+value[mid];
    if(temp>f[left][right])
    {
    f[left][right]=temp;
    path[left][right]=mid;
    }
    }
    }
    //cout<<"ok ";
    return f[left][right];
    }
    void printTree(int left,int right)
    {
    int mid=path[left][right];
    if(left>right)
    return ;
    cout<<(mid+1)<<" ";
    printTree(left,mid-1);
    printTree(mid+1,right);
    }
    void printhouTree(int left,int right)
    {
    int mid=path[left][right];
    if(left>right)
    return ;
    cout<<(mid+1)<<" ";
    printhouTree(mid+1,right);
    printhouTree(left,mid-1);

    }
    int main()
    {
    cin>>n;
    int i,j;
    for(i=0;i<n;i++)
    {
    cin>>value[i];
    for(j=0;j<n;j++)
    {
    f[i][j]=0;
    path[i][j]=-1;
    }
    }
    int sum;
    sum=search(0,n-1);
    cout<<sum<<endl;
    printTree(0,n-1);
    //cout<<endl;
    //printhouTree(0,n-1);
    return 0;
    }

  • 0
    @ 2016-10-03 21:32:27

    标准区间动态规划+搜索二分。

  • 0
    @ 2016-10-03 19:00:00
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    long long a[50], dp[50][50];
    int n, root[50][50];
    void print(int left,int right){
         if (left>right) return;
         printf("%d ",root[left][right]);
         print(left, root[left][right]-1);
         print(root[left][right]+1, right);
    }
    int main(){
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
            dp[i][i]=a[i];
            root[i][i]=i;
        }
        for (int i=n;i>0;i--)
            for (int j=i+1;j<=n;j++)
                for (int k=i;k<=j;k++){ 
                    if (dp[i][k-1]==0) dp[i][k-1]=1;
                    if (dp[k+1][j]==0) dp[k+1][j]=1;
                    if (dp[i][j] < (dp[i][k-1]*dp[k+1][j] + a[k])){
                         dp[i][j] = dp[i][k-1] *dp[k+1][j] + a[k];
                         root[i][j]=k;
                    }
        }
        printf("%I64d\n",dp[1][n]);
        print(1,n);
        return 0;
    }
    

信息

ID
1100
难度
2
分类
动态规划 | 树形DP 点击显示
标签
递交数
4331
已通过
2452
通过率
57%
上传者