【Test】动态规划专题 [2]

心已赠人 2022-01-07 15:21 242阅读 0赞

## 写在前面 ##

#### 【概况】 ####

时间四小时，总五题，写了三个题。

#### 【时间分配】 ####

看题花了很久(30min+)，总体上做题顺序 5->3->1(->4)。

#### 【问题】 ####

1.抓不住动态规划状态的设置，每个阶段子结构之间的关系。

2.总是YY出一些奇奇怪怪能过样例的奇怪贪心。

3.一点也没用到这几天学的dp新姿势...

## 正文在此 ##

### t1 ###

#### 【问题描述】 ####

有N棵小草，编号0至N-1。奶牛Bessie不喜欢小草，所以Bessie要用剪刀剪草，目标是使得这N棵小草的高度总和不超过H。在第0时刻，第i棵小草的高度是h\[i\]，接下来的每个整数时刻，会依次发生如下三个步骤：

（1）每棵小草都长高了，第i棵小草长高的高度是grow\[i\]。

（2）Bessie选择其中一棵小草并把它剪平，这棵小草高度变为0。注意：这棵小草并没有死掉，它下一秒还会生长的。

（3）Bessie计算一下这N棵小草的高度总和，如果不超过H，则完成任务，一切结束，否则轮到下一时刻。

你的任务是计算：最早是第几时刻，奶牛Bessie能完成它的任务？如果第0时刻就可以完成就输出0，如果永远不可能完成，输出-1，否则输出一个最早的完成时刻。

#### 【输入】 ####

第一行，两个整数N和H。 1 ≤ N ≤ 50，0 ≤ H ≤ 1000000。

第二行，N个整数，表示h\[i\]。0 ≤ h\[i\] ≤ 100000。

第三行，N个整数，表示grow\[i\]。1 ≤ grow\[i\] ≤ 100000。

#### 【输出】 ####

一个整数，最早完成时刻或-1。

#### 【输入输出样例1】 ####

<table> 
 <tbody> 
  <tr> 
   <td> <p>grass.in</p> </td> 
   <td> <p>grass.out</p> </td> 
  </tr> 
  <tr> 
   <td> <p>7 33</p> <p>5 1 6 5 8 4 7</p> <p>2 1 1 1 4 3 2</p> </td> 
   <td> <p>5</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 【做题过程】 ####

首先一个假假假假的贪心，把每个时刻的小草中最高的拔掉，发现连样例都推不出来。

再是一个高级的假贪心。到了第i个时刻时，如果不考虑剪草操作，第j棵草的贡献将是p\[j\].h+i\*p\[j\].g。

然后每次把贡献最高的减掉，每棵草的贡献分别减去g值，继续寻找最大值。

60分，代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//又是一个没有正确性的贪心 
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define File "grass"
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 55;
    int n,H;
    struct P{
        ll h,g;
        bool v;
    }p[mxn],t[mxn];
    inline bool cmp(P x,P y){
        return x.h>y.h;
    }
    
    ll s_st(0),s_g(0);
    int main(){
        file();
        scanf("%d %d",&n,&H);
        for(int i = 1;i <= n; ++i) scanf("%d",&p[i].h),s_st += p[i].h;
        for(int i = 1;i <= n; ++i) scanf("%d",&p[i].g),s_g += p[i].g,p[i].v = 0;
    
        if(s_st <= H){
            puts("0");
            return 0;
        }
        int tot(0);
        while(++tot){
    //        printf("tot:%d\n",tot);
            ll sum = s_st;
            for(int i = 1;i <= n; ++i) t[i] = p[i],p[i].v = 0,t[i].v = 0;
            sum += s_g*tot;
            for(int i = 1;i <= n; ++i)   p[i].h += 1ll*tot*p[i].g;
    
            for(int i = 1;i <= tot; ++i){
                sort(p+1,p+n+1,cmp);
                sum -= p[1].h;
                p[1].v = 1;
                p[1].h = 0;
    //            puts("**");
                for(int j = 1;j <= n; ++j)
                    if(p[j].v!=1) p[j].h -= p[j].g; 
            }    
    //        printf("sum:%lld %d\n",sum,H);
            if(sum<=H){
                printf("%d\n",tot);
                return 0;
            }
            for(int i = 1;i <= n; ++i) p[i] = t[i];
            if(tot > 100000){
                puts("-1");
                return 0;
            }
        }
        return 0;    
    } 
    /*
    7 33 
    5 1 6 5 8 4 7 
    2 1 1 1 4 3 2
    */

#### 【题解大意】 ####

由上面YY出来的贪心可以发现，选择删掉或者怎么删仿佛跟g有很大的关系。

先按照g从小到大排个序。

设f\[i\]\[j\]\[k\]为当前第i个时刻，枚举到第j棵小草，剪掉的小草为k个时 能剪掉的小草的最大高度值。

f\[i\]\[j\]\[k\] = max(f\[i-1\]\[j-1\]\[k\],f\[i-1\]\[j-1\]\[k-1\]+p\[j\].h+p\[j\].g\*k);

#### 【code】 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define File "grass"
    #define ll long long
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 55;
    int n,H;
    struct P{
        int h,g;
        friend bool operator <(P x,P y){
            return x.g==y.g ? x.h<y.h : x.g<y.g;
        }
    }p[mxn];
    int f[mxn][mxn];
    int s_g(0),s_h(0);
    int main(){
        file();
        n = read(),H = read();
        for(int i = 1;i <= n; ++i) p[i].h = read(),s_h += p[i].h;
        for(int i = 1;i <= n; ++i) p[i].g = read(),s_g += p[i].g;
        sort(p+1,p+n+1);
        if(s_h <= H){
            puts("0");  exit(0);
        }
        for(int i = 1;i <= n; ++i){
            int sum = s_h + s_g*i;
            memset(f,0,sizeof f);
            for(int j = 1;j <= n; ++j)
                for(int k = 1;k <= i; ++k)
                    f[j][k] = max(f[j-1][k],f[j-1][k-1]+p[j].h+p[j].g*k);
            if(sum - f[n][i] <= H){
                printf("%d\n",i);  exit(0);
            }
        }
        puts("-1");
        return 0;
    }
    /*
    7 33
    5 1 6 5 8 4 7
    2 1 1 1 4 3 2
    */

讲题的时候ybc提出这个dp可以n^2解决，代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define File "grass"
    #define ll long long
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 55;
    int n,H;
    struct P{
        int h,g;
        friend bool operator <(P x,P y){
            return x.g==y.g ? x.h<y.h : x.g<y.g;
        }
    }p[mxn];
    int f[mxn][mxn];
    int s_g(0),s_h(0);
    int main(){
        file();
        n = read(),H = read();
        for(int i = 1;i <= n; ++i) p[i].h = read(),s_h += p[i].h;
        for(int i = 1;i <= n; ++i) p[i].g = read(),s_g += p[i].g;
        sort(p+1,p+n+1);
        if(s_h <= H){
            puts("0");  exit(0);
        }
        /*
        for(int i = 1;i <= n; ++i){
            int sum = s_h + s_g*i;
            memset(f,0,sizeof f);
            for(int j = 1;j <= n; ++j)
                for(int k = 1;k <= i; ++k)
                    f[j][k] = max(f[j-1][k],f[j-1][k-1]+p[j].h+p[j].g*k);
            if(sum - f[n][i] <= H){
                printf("%d\n",i);  exit(0);
            }
        }*/
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= i; ++j)
                f[i][j] = max(f[i-1][j],f[i-1][j-1]+p[i].h+p[i].g*j);
        for(int i = 1;i <= n; ++i)
            if(s_h + s_g*i - f[n][i] <= H){
                printf("%d\n",i);
                exit(0);
            }
        puts("-1");
        return 0;
    }
    /*
    7 33
    5 1 6 5 8 4 7
    2 1 1 1 4 3 2
    */

### t2 ###

#### 【问题描述】 ####

现在有被划分为n个格子的一个圆环，每个格子上都有一个正整数，并且定义两个格子的距离为两个格子之间的格子数的最小值。

环的圆心处固定了一个指针，一开始指向了圆环上的某一个格子，你可以取下指针所指的那个格子里的数以及与这个格子距离小于k的格子的数，取一个数的代价即这个数的值。指针是可以转动的，每次转动可以将指针由一个格子转向其相邻的格子，且代价为圆环上还剩下的数的最大值。

对于给定的圆环和k，要求将所有数取完所有数的最小代价。

#### 【输入】 ####

输入文件的第1行有两个正整数n和k，描述了圆环上的格子数与取数的范围。

第2行有n个正整数，按顺时针方向描述了圆环上每个格子上的数，且指针一开始指向了第1个数字所在的格子。

所有整数之间用一个空格隔开，且不超过10000。

#### 【输出】 ####

输出文件仅包括1个整数，为取完所有数的最小代价。

#### 【输入输出样例1】 ####

<table> 
 <tbody> 
  <tr> 
   <td> <p>cirque.in</p> </td> 
   <td> <p>cirque.out</p> </td> 
  </tr> 
  <tr> 
   <td> <p>6 1</p> <p>4 1 2 3 1 3</p> </td> 
   <td> <p>21</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 【样例说明】 　　  ####

如上图所示，第一步不转动指针，取走4、3两个数，代价为7； 第2步指针顺时针转动2格，圆环上最大数为3，代价为6，取走1、2、3三个数，代价为6； 第3步指针顺时针转动1格，代价为1，取走剩下的一个数1，代价为1； 最小代价为7+6+6+1+1=21。

####  【数据规模】 ####

对于20%的数据，n≤10，k≤3；

对于40%的数据，n≤100，k≤10；

对于60%的数据，n≤500，k≤20；

#### 【看题心理】 ####

指针指来指去还在环上，看起来就是那种细节很多，调半个小时过了样例还wa得莫名其妙的题。

大概知道要贪心在指针指的第一个数附近尽量取，然后就把环变成了链，然后就可以区间dp?。

弃题弃题。。。

#### 【题解大意】 ####

好的，思路基本是对的。

首先预处理出区间\[l~r\]内的最大值(mx\[l\]\[r\]数组)以方便后面转移，O(n^2)。

然后套路地枚举区间长度，枚举左端点位置。

设置状态f\[i\]\[j\]\[0\]表示在左端点更新，l到r的最小代价。

同理f\[i\]\[j\]\[1\]表示右端点...

想到是否处于边界位置只能向一边转移。

状态转移方程为:

f\[l\]\[r\]\[0\] = min(f\[l\]\[r\]\[0\],f\[l\]\[r\]\[1\]+(n-len-1-2\*k)\*mx\[l\]\[r\]);

f\[l\]\[r\]\[1\] = min(f\[l\]\[r\]\[1\],f\[l\]\[r\]\[0\]+(n-len-1-2\*k)\*mx\[l\]\[r\]);

#### 【code】 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define File "cirque"
    #define inf 1<<30
    #define ll long long
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 2e3+5;
    int n,k;
    ll s(0);
    ll mn = inf;
    int a[mxn],mx[mxn][mxn];
    ll f[mxn][mxn][2];
    //0 left 1 right
    int main(){
    //    file();
        n = read(),k = read();
        for(int i = 1;i <= n; ++i) a[i] = read(),s = (ll)s+a[i];
        for(int i = 1;i <= n; ++i){
            mx[i][i] = a[i];
            for(int j = i+1;j <= n; ++j)
                mx[i][j] = max(mx[i][j-1],a[j]);
        }
    
        memset(f,0x3f,sizeof f);
        f[k+2][n-k][0] = f[k+2][n-k][1] = 0;
    
        for(int len = n-k*2-2; len >= 0; --len){
            for(int l = 1;l <= n-len+1; ++l){
                int r = len+l-1;
                ll d = n-r+l-2-2*k;
    
                if(l>1) f[l][r][0] = min(f[l-1][r][0] + mx[l-1][r],
                    f[l-1][r][1] + 1ll*d*mx[l-1][r]);
    
                if(r<n) f[l][r][1] = min(f[l][r+1][1] + mx[l][r+1],
                    f[l][r+1][0] + 1ll*d*mx[l][r+1]);
    
                f[l][r][0] = min(f[l][r][0],f[l][r][1]+1ll*d*mx[l][r]);
                f[l][r][1] = min(f[l][r][1],f[l][r][0]+1ll*d*mx[l][r]);
            }
        }
        for(int i = 2;i <= n; ++i)
            mn = min(min(mn,f[i][i-1][0]),f[i][i-1][1]);
        printf("%lld\n",mn+s);
        return 0;
    }
    /*
    6 1
    4 1 2 3 1 3
    
    */

### t3 ###

#### 【问题描述】 ####

给一棵n 个结点的有根树，结点由1 到n 标号，根结点的标号为1。每个结点上有一个物品，第i 个结点上的物品价值为vi。

你需要从所有结点中选出若干个结点，使得对于任意一个被选中的结点，其到根的路径上所有的点都被选中，并且选中结点的个数不能超过给定的上限lim。在此前提下，你需要最大化选中结点上物品的价值之和。

求这个最大的价值之和。

#### 【输入】 ####

第一行为两个整数n; lim

接下来n 行，第i 行包含一个整数vi，表示结点i 上物品的价值。

接下来n- 1 行，每行包含两个整数u; v, 描述一条连接u; v 结点的树边。

#### 【输出】 ####

输出一行答案。

#### 【输入输出样例1】 ####

#### 【数据范围】 ####

对于前20% 的数据，1<=n; lim<=10

对于前60% 的数据，1<=n; lim<=100

对于100% 的数据，1<=n; lim<=3000; |vi| <=10^5 数据有梯度，保证给出的是合法的树。

#### 【做题过程】 ####

看题的时候的标注上了树上背包dp，好，是道能好好写的题。

然后开始推式子，大概想的是：

f\[i\]\[j\]表示选取第i号节点，已经选了j个节点的最大花费。

f\[y\]\[k\] =max(f\[y\]\[k\]，f\[x\]\[k-1\]+w\[y\]);

其中第二维，因为从根节点到当前节点的路径上的点全部都要选取，所以预先处理了deep值，然后从lim到deep倒叙循环。

调了一会儿过了样例，但是只有10分我震惊。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//树上背包dp
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define File "tree"
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 3e3+5;
    int n,lim;
    struct edge{
        int nxt,y;
    }e[mxn<<1];
    
    int to[mxn],len;
    inline void add(int xx,int yy){
        e[++len].nxt = to[xx];
        to[xx] = len;
        e[len].y = yy;
    }
    
    int f[mxn][mxn],w[mxn];
    bool v[mxn];
    int d[mxn];
    //处理深度值
    inline void dfs(int x){
        v[x] = 1;
        for(int i = to[x]; i;i = e[i].nxt){
            int y = e[i].y;
            if(v[y]) continue;
            dfs(y);
            d[y] = d[x]+1;
        }
    }
    inline void dp(int x){
        v[x] = 1;
        for(int i = to[x]; i;i = e[i].nxt){
            int y = e[i].y;
            if(v[y]) continue;
            if(d[y]>lim) continue;
    //        dp(y);
            for(int j = lim; j > d[y]; --j)
                f[y][j] = max(f[x][j-1]+w[y],f[y][j]);
            dp(y);
        }
    }
    
    int main(){
        file();
        n = read(),lim = read();
        for(int i = 1;i <= n; ++i) w[i] = read();
        for(int i = 1;i < n; ++i){
            int u = read(),v = read();
            add(u,v),add(v,u);
        }
        memset(f,0xcf,sizeof f);
        f[1][1] = w[1];
        for(int i = 1;i <= n; ++i) f[i][0] = 0;
        dfs(1);
        memset(v,0,sizeof v);
        dp(1);
        int ans = 0;
        for(int i = 1;i <= n; ++i)
            for(int j = 0;j <= lim; ++j)
                ans = max(ans,f[i][j]);
    //    puts("");
        printf("%d\n",ans);
        return 0;
    }
    /*
    6 4
    -5
    4
    -6
    6
    9
    6
    3 2
    3 1
    2 4
    2 5
    1 6
    */

#### 【题解大意】 ####

其实前面的那个dp状态的设置是对的。虚神好像也是这么写的但是写出来也只有10分。

问题在于状态方程的转移。全场只有fcy一个人是O(n^2)的树形dp跑过去的，其余的满分都是用O(n^3)水的。

由于O(n^3)就能苟过去我没写O(n^2)的。

O(n^3)代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define File "tree"
    #define ll long long
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 3e3+5;
    int n,lim;
    int w[mxn],f[mxn][mxn],sz[mxn];
    struct edge{
        int y,nxt;
    }e[mxn<<1];
    
    int to[mxn],len;
    inline void add(int xx,int yy){
        e[++len].nxt = to[xx];
        to[xx] = len;
        e[len].y = yy;
    }
    
    inline void dfs(int x,int fa){
        sz[x] = 1;
        for(int i = lim;i >= 1; --i)    f[x][i] = f[x][i-1]+w[x];
        for(int i = to[x]; i;i = e[i].nxt){
            int y = e[i].y;
            if(y==fa) continue;
            dfs(y,x);
            sz[x] += sz[y];
            for(int j = lim;j >= 1; --j)
                for(int k = 1;k <= min(sz[y],j-1); ++k)
                    f[x][j] = max(f[x][j],f[x][j-k]+f[y][k]);
        }
    }
    
    int main(){
        file();
        n = read(),lim = read();
        for(int i = 1;i <= n; ++i) w[i] = read();
        for(int i = 1;i < n; ++i){
            int x = read(),y = read();
            add(x,y),add(y,x);
        }
    //    memset(f,0xcf,sizeof f);
        dfs(1,0);
        printf("%d\n",f[1][lim]);
        return 0;
    }
    /*
    /*
    s[x]=1;
        for(int j=m;j>=1;--j)
            f[x][j]=f[x][j-1]+v[x];
        for(int i=lin[x];i;i=e[i].nxt)
        {
            int y=e[i].y;
            if(y==fa)continue;
            dfs(y,x);
            s[x]+=s[y];
            for(int j=m;j>=1;--j)
                for(int k=1;k<=min(s[y],j-1);++k)
                    f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
        }
    }
    */
    /*
    6 4
    -5
    4
    -6
    6
    9
    6
    3 2
    3 1
    2 4
    2 5
    1 6
    */

fcy若干年前关于树形dp的一篇[博客][Link 1]，可以把很多O(n^3)的树形dp都变成O(n^2)的。

瓜皮太强啦。

具体说说O(n^2)的最优解变成了10分挂在哪里。

首先是再看之前列的状态转移方程：

f\[y\]\[k\] =max(f\[y\]\[k\]，f\[x\]\[k-1\]+w\[y\]);

从跟节点开始dfs那么显然到x节点的时候y节点是没有更新到的，所以f\[y\]\[k\]还是0（这里是我出错的原因

所以先将f\[y\]\[k\]赋值为f\[x\]\[k-1\]+w\[y\]，等处理完之后再f\[x\]\[k\] = max(f\[x\]\[k\],f\[y\]\[j\])一遍更新即可。

但是这样的代码只有20分，如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define File "tree"
    #define ll long long
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 3e3+5;
    int n,lim;
    int w[mxn],f[mxn][mxn],sz[mxn];
    struct edge{
        int y,nxt;
    }e[mxn<<1];
    
    int to[mxn],len;
    inline void add(int xx,int yy){
        e[++len].nxt = to[xx];
        to[xx] = len;
        e[len].y = yy;
    }
    
    inline void dfs(int x,int fa){
        for(int i = to[x]; i;i = e[i].nxt){
            int y = e[i].y;
            if(y==fa) continue;
            for(int j = 1;j <= lim; ++j) f[y][j] = f[x][j-1]+w[y];
            dfs(y,x);
            for(int j = 1;j <= lim; ++j) f[x][j] = max(f[x][j],f[y][j]);
        }
    }
    
    int main(){
        file();
        n = read(),lim = read();
        for(int i = 1;i <= n; ++i) w[i] = read();
        for(int i = 1;i < n; ++i){
            int x = read(),y = read();
            add(x,y),add(y,x);
        }
        f[1][1] = w[1];
        dfs(1,0);
        int ans = 0;
        for(int i = 1;i <= lim; ++i) ans = max(ans,f[1][i]);
        printf("%d\n",ans);
        return 0;
    }
    /*
    6 4
    -5
    4
    -6
    6
    9
    6
    3 2
    3 1
    2 4
    2 5
    1 6
    */

仔细观察了瓜皮的代码，发现枚举边的时候要倒序循环？。

#### 【code】 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    int n,lim,ip1,ip2,ans;
    int v[3050];
    vector<int>Link[3050];
    int f[3050][3050];
    int dfs(int x,int fa){
        for (int i=Link[x].size()-1;i>=0; --i)
            if(Link[x][i]!=fa){
                for (int j=1;j<=lim;++j)
                    f[Link[x][i]][j]=f[x][j-1]+v[Link[x][i]];
                dfs(Link[x][i],x);
                for (int j=1;j<=lim;++j)
                    f[x][j]=max(f[x][j],f[Link[x][i]][j]);
            }
    }
    int main(){
    //    freopen("tree.in","r",stdin);
    //    freopen("tree.out","w",stdout);
        memset(f,-0x3f,sizeof(f));
        scanf("%d%d",&n,&lim);
        for (int i=1;i<=n;++i) scanf("%d",&v[i]);
        for (int i=1;i<n;++i){
            scanf("%d%d",&ip1,&ip2);
            Link[ip1].push_back(ip2);
            Link[ip2].push_back(ip1);
        }
        f[1][1]=v[1];
        dfs(1,0);
    
        for (int i=1;i<=lim;++i)
            ans=max(ans,f[1][i]);
        printf("%d",ans);
        return 0;
    }

### t4 ###

#### 【问题描述】 ####

机房最近决定举行一场锦标赛。锦标赛共有N个人参加，共进行N-1轮。第一轮随机挑选两名选手进行决斗，胜者进入下一轮的比赛，第二轮到第N-1轮再每轮随机挑选1名选手与上一轮胜利的选手决斗，最后只剩一轮选手。第i名选手与第j名选手决斗，第i名选手胜利的概率是a\[i\]\[j\].

作为一号选手的小x想知道如何安排每轮出场的选手可以使得他获胜的概率最大，并求出这个最大概率。

#### 【输入】 ####

第一个一个整数N，表示参赛人数。

接下来N行，每行N个小数表示a\[i\]\[j\]

保证满足a\[i\]\[i\]=0，a\[i\]\[j\]+a\[j\]\[i\]=1；

#### 【输出】 ####

一个小数，表示最大概率。与答案误差不超过10^(-5) 即算正确。

#### 【输入输出样例1】 ####

<table> 
 <tbody> 
  <tr> 
   <td> <p>combat.in</p> </td> 
   <td> <p>combat.out</p> </td> 
  </tr> 
  <tr> 
   <td> <p>3</p> <p>0.0 0.5 0.8</p> <p>0.5 0.0 0.4</p> <p>0.2 0.6 0.0</p> </td> 
   <td> <p>0.6800000</p> </td> 
  </tr> 
 </tbody> 
</table>

样例解释

第一轮2与3决斗，胜者与1决斗

如果2获胜，那么最后1获胜的概率为a\[2\]\[3\]\*a\[1\]\[2\]=0.2

如果3获胜，那么最后1获胜的概率为a\[3\]\[2\]\*a\[1\]\[3\]=0.48

所以总概率为0.68

#### 【数据范围】 ####

对于30%的数据，N<=10  
对于60%的数据，N<=15  
对于100%的数据，N<=18

####  【看题过程】 ####

数据范围疯狂暗示这是个状压dp，但是我不是很会状压，考场上是不是可以偷偷放一放，有多的时间慢慢写。

#### 【题解大意】 ####

状压dp。

f\[s\]表示集合s时1获胜的概率。

需特别注意这里数组都要从0为下标开始。

具体实现看代码。

#### 【code】 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define File "combat"
    #define ll long long
    #define ull unsigned long long
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    const int mxn = 20;
    int n;
    double f[1<<mxn],a[mxn][mxn];
    int main(){
    //    file();
        scanf("%d",&n);
        for(int i = 0;i < n; ++i)
            for(int j = 1;j < n; ++j)
                cin >> a[i][j];
    
        f[1] = 1.0;
        for(int s = 1; s < (1<<n); ++s){
            for(int i = 0;i < n; ++i){
                if(s>>i&1){
                    for(int j = 0;j < n; ++j)
                        if(s>>j&1) f[s] = max(f[s], f[s^(1<<i)] * a[j][i] + f[s^(1<<j)] * a[i][j]);
                }
            }
        }
        printf("%.7f\n",f[(1<<n)-1]);
        return 0;
    }
    /*
    3
    0.0 0.5 0.8
    0.5 0.0 0.4
    0.2 0.6 0.0
    */

### t5 ###

#### 【问题描述】 ####

我们需要将一个文件复制到n个服务器上，这些服务器的编号为S1, S2, …, Sn。

首先，我们可以选择一些服务器，直接把文件复制到它们中；将文件复制到服务器Si上，需要花费ci > 0的置放费用。对于没有直接被复制文件的服务器Si来说，它依次向后检查Si+1, Si+2, …直到找到一台服务器Sj：Sj中的文件是通过直接复制得到的，于是Si从Sj处间接复制得到该文件，这种复制方式的读取费用是j – i（注意j>i）。另外，Sn中的文件必须是通过直接复制得到的，因为它不可能间接的通过别的服务器进行复制。我们设计一种复制方案，即对每一台服务器确定它是通过直接还是间接的方式进行复制（Sn只能通过直接方式），最终使每一台服务器都得到文件，且总花费最小。

#### 【输入】 ####

输入文件的第一行有一个整数n，表示服务器的数目。

输入文件的第二行有n个整数，顺数第i个表示ci：在Si上直接复制文件的费用。

#### 【输出】 ####

输出文件中只包含一个整数，即最少需要花费的费用。

#### 【输入输出样例1】 ####

<table> 
 <tbody> 
  <tr> 
   <td> <p>server.in</p> </td> 
   <td> <p>server.out</p> </td> 
  </tr> 
  <tr> 
   <td> <p>10</p> <p>2 3 1 5 4 5 6 3 1 2</p> </td> 
   <td> <p>18</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 【数据范围】 ####

60%的数据中，1 <= n <= 1 000

100%的数据中，1 <= n <= 1 000 000

80%的数据中， 1 <= ci <= 50

100%的数据中，1 <= ci <= 1 000 000 000

最终结果可能较大，请注意选择适当的数据类型进行计算。

#### 【做题过程】 ####

很快YY出一个dp，大概知道要用斜率优化，脑抽60分的O(n^2)，被我每次用一个数组记录最优解由什么转移而来，优化成O(n)，只有20分。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define File "server"
    inline void file(){
        freopen(File".in","r",stdin);
        freopen(File".out","w",stdout);
    }
    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<<1)+(x<<3)+ch-'0'; ch=getchar();}
        return x*f;
    }
    const int mxn = 1e6+5;
    int n;
    int c[mxn],f[mxn][2];
    int main(){
    //    file();
        n = read();
        for(int i = 1;i <= n; ++i) c[i] = read();
        memset(f,0x3f,sizeof f);
        f[n][1] = f[n][0] = c[n];
        for(int i = n-1; i; --i){
            for(int j = i+1;j <= n; ++j)
                f[i][0] = min(f[i][0],f[j][1]+(j-i+1)*(j-i)/2);//间接复制
            f[i][1] = min(f[i+1][1],f[i+1][0]) + c[i];//直接复制
        }
        printf("%d\n",min(f[1][1],f[1][0]));
        return 0;
    }
    
    /*
    4
    3 10 2 4
    10
    2 3 1 5 4 5 6 3 1 2
    */

#### 【题解大意】 ####

暴力dp是这样的：  
直接复制:f\[i\]\[1\] = min(f\[i+1\]\[0\],f\[i+1\]\[1\])+c\[i\];

间接复制:f\[i\]\[0\] = min(f\[i\]\[0\],f\[j\]\[1\]+(j-i+1)\*(j-i)/2);  (i+1 <= j <= n)

f\[n\]\[1\] = c\[n\],其余赋值为正无穷。

然后考虑如何对间接复制的方程进行斜率优化，推式子跟之前的几篇博客差不多吧，都是套路。

#### 【code】 ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    int N,Head=1,Tail=0,Q[1000010]={};
    long long C[1000010]={},F[1000010][2]={};
    long long Val(int x){
        return F[x][0]+((long long)x+1)*x/2;
    }
    double Calc(int x,int y){
        return (Val(x)-Val(y))*1.0/(x-y);
    }
    int main(){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%lld",&C[i]);
        for(int i=1;i<=N;i++) F[i][0]=222222222222;
        F[N][0]=C[N]; F[N][1]=222222222222;
        Q[++Tail]=N;
    //    printf("%d\n",Tail);
        for(int i=N-1;i>=1;i--){
            F[i][0]=min(F[i+1][0],F[i+1][1])+C[i];
            
            for(;Head+1<=Tail&&Calc(Q[Head],Q[Head+1])>=i;Head++);
            F[i][1]=F[Q[Head]][0]+((long long)Q[Head]-i+1)*(Q[Head]-i)/2;
            for(;Head+1<=Tail&&Calc(Q[Tail],i)>Calc(Q[Tail-1],Q[Tail]);Tail--);
            Q[++Tail]=i;
            printf("l,r:%d %d\n",Head,Tail);
            printf("f[i][0]:%d f[i][1]:%d\n",F[i][0],F[i][1]);
        }
        printf("%lld\n",min(F[1][0],F[1][1]));
        return 0;
    }

转载于:https://www.cnblogs.com/ve-2021/p/10864256.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/e7b47c0bcb1445078996a1bf8f220c4d.png
[Link 1]: https://opportunityfan.coding.me/2018/09/02/%E5%9B%9E%E5%A4%B4%E7%9C%8B%E7%9C%8B%E5%8F%91%E7%8E%B0%E8%87%AA%E5%B7%B1%E9%9D%9E%E5%B8%B8%E5%BC%B1%E6%99%BA%E7%9A%84%E6%A0%91%E4%B8%8A%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85DP/