记忆化搜索真是玄学。。
本来只是想写个暴力为啥空间改大就AC了？？
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const LL inf=(1LL<<61); inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline LL LLread() { LL x=0LL,f=1LL;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1LL;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10LL+(LL(ch-'0'));ch=getchar();} return x*f; } struct node { int lc,rc; }tr[41000]; int n;LL f[41000][40][40];//点，上方x值，上方y值 LL A[41000],B[41000],C[41000]; void treeDP(int now,int x,int y) { if(f[now][x][y]<inf)return ; if(now>n) { f[now][x][y]=C[now]*(A[now]+LL(x))*(B[now]+LL(y)); return ; } int lc=tr[now].lc,rc=tr[now].rc; treeDP(lc,x,y), treeDP(rc,x,y+1); treeDP(lc,x+1,y), treeDP(rc,x,y); f[now][x][y]=min(f[lc][x][y]+f[rc][x][y+1],f[lc][x+1][y]+f[rc][x][y]); } int main() { int x,y; n=read(); for(int i=1;i<n;i++) { x=read();y=read(); if(x<0)x=n+abs(x); if(y<0)y=n+abs(y); tr[i].lc=x,tr[i].rc=y; } for(int i=n+1;i<=n+n;i++)A[i]=LLread(),B[i]=LLread(),C[i]=LLread(); memset(f,63,sizeof(f)); treeDP(1,0,0); printf("%lld ",f[1][0][0]); return 0; }