[关闭]
@ysner 2018-07-25T10:49:14.000000Z 字数 1872 阅读 1957

[NOI2009]二叉查找树

DP


题面

戳我

解析

我刚看到这道题时无从下手,连状态都不知道怎么设。。。
于是坠入题解的深渊

根据定义,该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大,而比它右儿子结点的数据值小。
则因数据值不会被修改,所以树的中序遍历不变(先左再中后右)。
于是我们可以在树的中序遍历上进行区间,一个区间就能代表一颗子树。

又因为是否加上代价取决于子树根结点与其祖先结点的关系(权值不能比祖先小,否则你把哪个点当整个树的根都可以),我们应该在状态中维护该子树根节点的值。即状态为表示在区间内,根节点权值为的子树的访问代价。

于是就可以列转移方程式:(是访问频率前缀和)


又注意到数据范围似乎很大(),由于权值只要比较相对大小就可以了,直接离散化(然后我的离散化因为一开始不排序而gg!!!详见代码注释部分)。
我选择了写着更舒服的记搜。。。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define re register
  8. #define il inline
  9. #define ll long long
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. struct node{ll dat,w,v;bool operator < (const node &o) const{return dat<o.dat;}}a[100];
  16. struct pzy{ll w,id;bool operator < (const pzy &o) const{return w<o.w;}}b[100];
  17. ll n,k,o[100],s[100],len,dp[100][100][100];
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il ll dfs(re int l,re int r,re int w)
  28. {
  29. re ll ans=2e9;
  30. if(dp[l][r][w]!=-1) return dp[l][r][w];
  31. if(l>r) return dp[l][r][w]=0;
  32. fp(i,l,r)
  33. {
  34. if(a[i].w>=w) ans=min(ans,dfs(l,i-1,a[i].w)+dfs(i+1,r,a[i].w)+s[r]-s[l-1]);
  35. ans=min(ans,dfs(l,i-1,w)+dfs(i+1,r,w)+s[r]-s[l-1]+k);
  36. }
  37. return dp[l][r][w]=ans;
  38. }
  39. int main()
  40. {
  41. memset(dp,-1,sizeof(dp));
  42. n=gi();k=gi();
  43. fp(i,1,n) a[i].dat=gi();fp(i,1,n) a[i].w=gi(),o[i]=a[i].w;fp(i,1,n) a[i].v=gi();
  44. //len=unique(o+1,o+1+n)-o-1;
  45. //fp(i,1,n) a[i].w=lower_bound(o+1,o+1+len,a[i].w)-o;
  46. sort(a+1,a+1+n);
  47. fp(i,1,n) b[i].w=a[i].w,b[i].id=i;
  48. sort(b+1,b+1+n);
  49. fp(i,1,n) a[b[i].id].w=i;
  50. fp(i,1,n) s[i]=s[i-1]+a[i].v;
  51. //这里不要预处理dp[l][r][w]=k之类,上面能处理
  52. printf("%lld\n",dfs(1,n,1));
  53. return 0;
  54. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注