题解 P1270 【“访问”美术馆】

liumingchen · 2016-03-19 11:27:02 · 题解

一个有趣的树形动规。。。。

注意可以不把一个展厅的画取完，害的我找了半天的错。。

可以在每个叶节点（非展厅）把剩余时间与偷的画的数量记录下来

附上代码：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
struct qe
{
    int is,t,fa,l[3],r;
}map[1000];
int n=1,ti;
int qw[103][603];
int we(int a,int b)
{
    if(b>a) return a;
    return b;
}
int work(int a,int time)
{
    if(qw[a][time]!=-1) return qw[a][time];    
    if(map[a].is!=0)
    if(map[a].t<=time) 
    {qw[a][time]=we(map[a].is,(time-map[a].t)/5);
    return qw[a][time];
    }
    else 
    {qw[a][time]=0;
    return 0;
    }    
    if(time-map[a].t<=0) return 0;
    time-=map[a].t;
    int l=map[a].l[1],r=map[a].l[2];
    int max=0;
    for(int i=0;i<=time;i++) 
    {
        int t1,t2;
        t1=work(l,time-i);
        t2=work(r,i);
        if(t1+t2>max) max=t1+t2;    
    }
    qw[a][time+map[a].t]=max;
    return max;
}
int main()
{
    int i,j,k;
    scanf("%d",&ti);
    for(i=1;;i++)
    {
        scanf("%d%d",&map[i].t,&map[i].is);
        map[i].r=1;
        if(i!=1)
        {
            for(j=i-1;j>=1;j--)
            {
                if(map[j].is==0&&map[j].r!=3)
                {
                    map[i].fa=j;
                    map[j].l[map[j].r]=i;
                    map[j].r++;
                    break;
                }
            }
        }
        int p=1;
        for(j=1;j<=i;j++) if(map[j].r!=3&&map[j].is==0) p=0;
        if(p==1) break;
    }
    n=i;
    for(i=1;i<=n;i++) 
    {
        map[i].t*=2;
    }
    for(i=1;i<=n;i++)for(j=0;j<=ti;j++) qw[i][j]=-1;
    int ans;
    ans=work(1,ti);    
    printf("%d",ans);    
    return 0;
}