[NOI day1 2009 二叉查找树]区间动态规划

【题目大意】

给定一个Treap的结点，然后你可以修改某些权值，每修改一个权值，花费K的代价。然后整棵树的权为各点的权和，而点的权定义为深度*给定的频率。让你求修改权值+树权最小是多少。

【算法分析】

注意到一点，由于权值可以改变，所以它不一定还是满足原来性质的堆，但是由于数据值是不能改变的，所以它必然还是一颗二叉查找树。

如果中序遍历一颗二叉查找树的话，就会得到一个排好序的序列。

所以可以想象如果从叶子往上面合的话，相当于每次在连续的一段里取一个结点做子树的根，然后合并这个结点两边的子树。

所以可以看成是经典的区间型动态规划。

f[i,j,W]表示[i,j]这个区间内够成一棵子树，该子树的树根的权值>=W的最小权。

然后首先有f[i,j,W]=f[i,j,W+1]

然后如果i>j的话，取为0。

剩下的就是看修不修改权值了。

f[i,j,W]=max{

f[i,k-1,W]+f[k+1,j,W]+s[i,j]+K（修改权值）

f[i,k-1,w[k]]+f[k+1,j,w[k]]+s[i,j] (前提是w[k]>=W,这就对应不修改权值)

}

【其它】WA了一遍。。。囧，memset这东西在long long身上好像有点不同，以后不用就是。

【CODE】

#include #include using namespace std;
const long long N=72;
const long long inf=(long long)(0x7FFFFFFF/2)*(long long)(0x7FFFFFFF/2);
long long n,cost;
long long key[N],w[N],ss[N],f[N][N][N],s[N][N];
long long pos[N],lw[N];

void init(){
    cin >> n >> cost;
    for (long long i=1;i<=n;i++) cin >> key[i];
    for (long long i=1;i<=n;i++) cin >> w[i];
    for (long long i=1;i<=n;i++) cin >> ss[i];
    for (long long i=1;i<=n;i++){
        pos[i]=i;
        lw[i]=w[i];
    }   
}   

void sort(){
    long long i,j,tmp;
    for (i=1;i      for (j=i+1;j<=n;j++)
        if (lw[i]>w[j]){
            tmp=lw[i]; lw[i]=lw[j]; lw[j]=tmp;
            tmp=pos[i]; pos[i]=pos[j]; pos[j]=tmp;
        }
    for (i=1;i<=n;i++) w[pos[i]]=i;
    for (i=1;i      for (j=i+1;j<=n;j++)
        if (key[i]>key[j]){
            tmp=key[i]; key[i]=key[j]; key[j]=tmp;
            tmp=w[i]; w[i]=w[j]; w[j]=tmp;
            tmp=ss[i]; ss[i]=ss[j]; ss[j]=tmp;
        }
    for (i=1;i<=n;i++){
      s[i][i]=ss[i];
      for (j=i+1;j<=n;j++)
        s[i][j]=s[i][j-1]+ss[j];
    }   
}   

void work(){
    long long len,i,j,k,W;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        f[i][j][n+1]=inf;
    for (i=0;i<=n;i++)
      for (k=1;k<=w[i];k++)
        f[i][i][k]=ss[i];
    for (len=0;len      for (i=1;i+len<=n;i++){
          j=i+len;
          for (W=n;W>=0;W–){
            f[i][j][W]=f[i][j][W+1];
            for (k=i;k<=j;k++){
              if (f[i][k-1][W]+f[k+1][j][W]+s[i][j]+cost                f[i][j][W]=f[i][k-1][W]+f[k+1][j][W]+s[i][j]+cost;
              if (w[k]>=W && f[i][k-1][w[k]]+f[k+1][j][w[k]]+s[i][j]                f[i][j][W]=f[i][k-1][w[k]]+f[k+1][j][w[k]]+s[i][j];
            }   
          }   
      }
    cout << f[1][n][1] << endl;
}   

int main(){
    freopen("treapmod.in","r",stdin);
    freopen("treapmod.out","w",stdout);
    init();
    sort();
    work();
    return 0;
}