简单暴力到dp的优化(中级篇）

女爷i 2022-05-18 05:48 125阅读 0赞

下面再放三道我比较喜欢的，需要好好写一下的题。

第一题比较水

1. White Cloud is exercising in the playground. White Cloud can walk 1 meters or run k meters per second. Since White Cloud is tired,it can't run for two or more continuous seconds. White Cloud will move L to R meters. It wants to know how many different ways there are to achieve its goal. Two ways are different if and only if they move different meters or spend different seconds or in one second, one of them walks and the other runs.

输入描述： The first line of input contains 2 integers Q and k.Q is the number of queries.(Q<=100000,1<=k<=100000) For the next Q lines,each line contains two integers L and R.(1<=L<=R<=100000)

输出描述： For each query,print a line which contains an integer,denoting the answer of the query modulo 1000000007.

示例1: 输入 3 3 3 3 1 4 1 5 输出 2 7 11

题目大意

白云在健身，每秒可以走1米或跑k米，并且不能连续两秒都在跑。 当它的移动距离在\[L,R\]之间时，可以选择结束锻炼。 问有多少种方案结束。

做法

DP? f\[i\]\[0/1\]表示已经过了i米，最后一步是跑还是走的方案数，分开就很好写了，简单，自己体会。 f\[i\]\[1\]=f\[i-k\]\[0\],f\[i\]\[0\]=f\[i-1\]\[0\]+f\[i-1\]\[1\] 。注意要记录前缀和。

#include <bits/stdc++.h>
    #define MOD 1000000007
    using namespace std;
    typedef long long ll;
    ll g[100005];
    ll dp[100005][2];
    int main(void)
    {
        int q,k,a,b;
        ll sum;
        cin>>q>>k;
        dp[0][0]=1;
        for(int i=1;i<=100000;++i){
            dp[i][0]=(dp[i-1][0]+dp[i-1][1])%MOD;
            if(i-k>=0)dp[i][1]=(dp[i-k][0])%MOD;
        }
        sum=0;
        for(int i=1;i<=100000;++i){
            g[i]=(dp[i][0]+dp[i][1]+sum);
            sum=g[i];
        }
        // for(int i=9000;i<=100000;++i){
        //     cout<<g[i]<<endl;
        // }
        while(q--){
            cin>>a>>b;
            cout<<(g[b]-g[a-1])%MOD<<endl;
        }
        return 0;
    }

2、来一发多重背包

选这个题是感觉代码有一种美感。。。。。

一. 编程题

1. Since then on, Eddy found that physics is actually the most important thing in the contest. Thus, he wants to form a team to guide the following contestants to conquer the PACM contests(PACM is short for Physics, Algorithm, Coding, Math).

There are N candidate groups each composed of pi physics experts, ai algorithm experts, ci coding experts, mi math experts. For each group, Eddy can either invite all of them or none of them. If i-th team is invited, they will bring gi knowledge points which is calculated by Eddy's magic formula. Eddy believes that the higher the total knowledge points is, the better a team could place in a contest. But, Eddy doesn't want too many experts in the same area in the invited groups. Thus, the number of invited physics experts should not exceed P, and A for algorithm experts, C for coding experts, M for math experts.

Eddy is still busy in studying Physics. You come to help him to figure out which groups should be invited such that they doesn't exceed the constraint and will bring the most knowledge points in total.

输入描述： The first line contains a positive integer N indicating the number of candidate groups. Each of following N lines contains five space-separated integer p i, ai, ci, mi, gi indicating that i-th team consists of pi physics experts, ai algorithm experts, ci coding experts, mi math experts, and will bring gi knowledge points. The last line contains four space-separated integer P, A, C, M indicating the maximum possible number of physics experts, algorithm experts, coding experts, and math experts, respectively.

1 ≤ N ≤ 36 0 ≤ pi,ai,ci,mi,gi ≤ 36 0 ≤ P, A, C, M ≤ 36

输出描述： The first line should contain a non-negative integer K indicating the number of invited groups. The second line should contain K space-separated integer indicating the index of invited groups(groups are indexed from 0).

You can output index in any order as long as each index appears at most once. If there are multiple way to reach the most total knowledge points, you can output any one of them. If none of the groups will be invited, you could either output one line or output a blank line in the second line.

题干有点长，其实就是每个队有四种代价，一个价值。多重背包。36的五次方竟然没超时也是醉了。。

#include <bits/stdc++.h>
    using namespace std;
    const int N=37;
    int n, p[N], a[N], c[N], m[N], g[N];
    int P, A, C, M;
    short dp[N][N][N][N][N];
    bool tk[N][N][N][N][N];
    int main(){
      cin>>n;
      for(int i=0; i<n; i++)
        cin>>p[i]>>a[i]>>c[i]>>m[i]>>g[i];
      cin>>P>>A>>C>>M;
      for(int i=0; i<=n; i++)
        for(int ip=0; ip<=P; ip++)
          for(int ia=0; ia<=A; ia++)
            for(int ic=0; ic<=C; ic++)
              for(int im=0; im<=M; im++)
                tk[i][ip][ia][ic][im]=false;
      for(int i=0; i<n; i++){
        for(int ip=P; ip>=0; ip--)
          for(int ia=A; ia>=0; ia--)
            for(int ic=C; ic>=0; ic--)
              for(int im=M; im>=0; im--)
                dp[i+1][ip][ia][ic][im]=dp[i][ip][ia][ic][im];
        for(int ip=P; ip>=p[i]; ip--)
          for(int ia=A; ia>=a[i]; ia--)
            for(int ic=C; ic>=c[i]; ic--)
              for(int im=M; im>=m[i]; im--)
                if(dp[i][ip-p[i]][ia-a[i]][ic-c[i]][im-m[i]]+g[i]>
                   dp[i+1][ip][ia][ic][im]){
                  dp[i+1][ip][ia][ic][im]=dp[i][ip-p[i]][ia-a[i]][ic-c[i]][im-m[i]]+g[i];
                  tk[i+1][ip][ia][ic][im]=true;
                }
      }
      fprintf(stderr, "ans=%d\n", dp[n][P][A][C][M]);
      vector<int> ans;
      for(int i=n; i>=1; i--)
        if(tk[i][P][A][C][M]){
          ans.push_back(i-1);
          P-=p[i-1];
          A-=a[i-1];
          C-=c[i-1];
          M-=m[i-1];
        }
      reverse(ans.begin(), ans.end());
      printf("%d\n", (int)ans.size());
      for(size_t i=0; i<ans.size(); i++)
        printf("%d%c", ans[i], " \n"[i+1==ans.size()]);
    }

# **3、****P1040 加分二叉树** #

题目

[https://www.luogu.org/problemnew/show/P1040][https_www.luogu.org_problemnew_show_P1040]

设一个 nn 个节点的二叉树tree的中序遍历为（ 1,2,3,…,n1,2,3,…,n ），其中数字 1,2,3,…,n1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 ii 个节点的分数为 di,treedi,tree 及它的每个子树都有一个加分，任一棵子树 subtreesubtree （也包含 treetree 本身）的加分计算方法如下：

subtreesubtree 的左子树的加分× subtreesubtree 的右子树的加分＋ subtreesubtree 的根的分数。

若某个子树为空，规定其加分为 11 ，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（ 1,2,3,…,n1,2,3,…,n ）且加分最高的二叉树 treetree 。要求输出；

（1） treetree 的最高加分

（2） treetree 的前序遍历

思路：这个题可以用动态规划或者记忆化搜索来做。因为如果要求加分最大的话，必须要求它的儿子结点加分最大，所以就有了最优子阶段。我们可以枚举根来更新最大值。

root\[i,j\]表示\[i,j\]这段序列的根，递归输出先序遍历。注意初始化，f\[i\]\[i\]=v\[i\]，当序列只有I一个元素时，f\[i\]\[i\]等于这个点本身的权值，当l==r-1时，此时是空树设为1。

#include<iostream>
    #include<cstdio>
    using namespace std;
    int n,v[39],f[47][47],i,j,k,root[49][49];
    void print(int l,int r){
        if(l>r)return;
        if(l==r){printf("%d ",l);return;}
        printf("%d ",root[l][r]);
        print(l,root[l][r]-1);
        print(root[l][r]+1,r);
    }
    int main() {
        scanf("%d",&n);
        for( i=1; i<=n; i++) scanf("%d",&v[i]);
        for(i=1; i<=n; i++) {f[i][i]=v[i];f[i][i-1]=1;}
        for(i=n; i>=1; i--)
            for(j=i+1; j<=n; j++)
                for(k=i; k<=j; k++) {
                    if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {
                        f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                        root[i][j]=k;
                    }
                }
        printf("%d\n",f[1][n]);
        print(1,n);
        return 0;
    }

[https_www.luogu.org_problemnew_show_P1040]: https://www.luogu.org/problemnew/show/P1040