传送门 改变后的权值不能相同 但是由于可以改成任意实数 而且代价与更改的大小无关 所以其实相同与否无所谓了 所以题目有时也有废话 首先键值是不能更改的 而一棵treap的中序遍历保证键值递增 故中序遍历一定 我们先按照键值排序得到中序遍历 w很大 但是保证不重复 所以我们将w离散化 然后就是DP的问题了。。我们令f[i][j][w]表示从i~j的节点构成一棵子树且所有节点权值都大于等于w的最小代价 那么状态转移时枚举新子树的根节点k 有两种更新方式 1.直接将k的权值改为w 则f[i][j][w]=min( f[i][j][w] , f[i][k-1][w] + f[k+1][j][w] + K + i~j的访问频率之和 ); 2.若k的权值大于等于w 则f[i][j][w]=min( f[i][j][w] , f[i][k-1][a[k].weight] + f[k+1][j][a[k].weight] + i~j的访问频率之和 ); 状态是n^3，枚举k是n，一共O(n^4)，n<=70，刚好卡过去
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #define M 80 #define inf 0x3f3f3f3f using namespace std; struct data{int x,y,z;}a[M]; bool cmp(data a,data b){return a.x<b.x;} pair<int,int> b[M]; int f[M][M][M],n,p,ans; int main(){ scanf("%d%d",&n,&p); for (int i=1;i<=n;i++) scanf("%d",&a[i].x); for (int i=1;i<=n;i++) scanf("%d",&a[i].y); for (int i=1;i<=n;i++) scanf("%d",&a[i].z); sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++) b[i].first=a[i].y,b[i].second=i; sort(b+1,b+n+1); for (int i=1;i<=n;i++) a[b[i].second].y=i; for (int i=1;i<=n;i++) a[i].z+=a[i-1].z; memset(f,inf,sizeof(f)); for (int i=1;i<=n+1;i++) for (int j=0;j<=n;j++) f[i][i-1][j]=0; for (int l=n;l>=1;l--) for (int i=n;i>=1;i--) for (int j=i;j<=n;j++) for (int k=i;k<=j;k++){ if (a[k].y>=l) f[i][j][l]=min(f[i][j][l],f[i][k-1][a[k].y]+f[k+1][j][a[k].y]+a[j].z-a[i-1].z); f[i][j][l]=min(f[i][j][l],f[i][k-1][l]+f[k+1][j][l]+p+a[j].z-a[i-1].z); } ans=inf; for (int i=0;i<=n;i++) ans=min(ans,f[1][n][i]); printf("%d",ans); }