LCX的算法笔记Week-4

动态规划

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

  • 朴素版（从定义出发）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,v;
int vi[N],wi[N];
int f[N][N];
int main() {
    cin>>n>>v;
    for (int i=1; i<=n; i++) {
        cin>>vi[i]>>wi[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=v; j++) {
            f[i][j]=f[i-1][j];
            if (j>=vi[i]) {
                f[i][j]=max(f[i][j],f[i-1][j-vi[i]]+wi[i]);
            }
        }
    }
    cout<<f[n][v];
    return 0;
}
  • 等价优化版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,v;
int vi[N],wi[N];
int f[N];
int main() {
    cin>>n>>v;
    for (int i=1; i<=n; i++) {
        cin>>vi[i]>>wi[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=v; j>=vi[i]; j--) {
                f[j]=max(f[j],f[j-vi[i]]+wi[i]);
        }
    }
    cout<<f[v];
    return 0;
}

完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

和01背包类似，写出递推关系，然后化简一下递推关系

  • 朴素版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,v;
int vi[N],wi[N];
int f[N][N];
int main() {
    cin>>n>>v;
    for (int i=1; i<=n; i++) {
        cin>>vi[i]>>wi[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=v; j++) {
            f[i][j]=f[i-1][j];
            if (j>=vi[i]) {
                f[i][j]=max(f[i][j],f[i][j-vi[i]]+wi[i]);
            }
        }
    }
    cout<<f[n][v];
    return 0;
}
  • 等价优化版（和01背包优化思路类似，只需要让j从递减变成递增，这也体现在朴素版代码唯一的不同，一个是i，一个是i-1）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,v;
int vi[N],wi[N];
int f[N];
int main() {
    cin>>n>>v;
    for (int i=1; i<=n; i++) {
        cin>>vi[i]>>wi[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=vi[i]; j<=v; j++) {
                f[j]=max(f[j],f[j-vi[i]]+wi[i]);
        }
    }
    cout<<f[v];
    return 0;
}

多重背包问题

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值

  • 朴素版（直接穷举所有状态）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main() {
    cin>>n>>m;
    for (int i=1; i<=n; i++) {
        cin>>v[i]>>w[i]>>s[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=m; j++) {
            for (int k=0; k*v[i]<=j&&k<=s[i]; k++) {
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

当物品数量足够多的时候，我们一条条来枚举肯定会超时的，所以就有了二进制优化版

核心思想是任何一个数都有一个二进制表示方法，所以我们把1、2、4、8、…..、2n个物品绑在一起，把他们当为不同的物品，然后进行01背包的枚举（可以覆盖之前的所有情况），就能将时间复杂度从O(n3)降到O(n2logn)。

  • 二进制优化版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e6+10;
    int n,m,cnt;
    int v[N],w[N];
    int f[N];
    int main() {
        cin>>n>>m;
        while (n--) {
            int x,y,z;
            cin>>x>>y>>z;
            int k=1;
            while (k<z) {
                v[++cnt]=k*x;
                w[cnt]=k*y;
                z-=k;
                k<<=1;
            }
            if (z) {
                v[++cnt]=z*x;
                w[cnt]=z*y;
            }
        }
        for (int i=1; i<=cnt; i++) {
            for (int j=m; j>=v[i]; j--) {
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
        cout<<f[m];
        return 0;
    }

    分组背包问题

    有 N 组物品和一个容量是 V 的背包。

    每组物品有若干个，同一组内的物品最多只能选一个。
    每件物品的体积是v ij，价值是 wij，其中 i 是组号，j 是组内编号。

    求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

    输出最大价值。

    f[i] [j]=max(f[i] [j],f[i-1] [j-v[i] [k]]+w[i] [k])

    f[i] [j]表示拿到第i组此时背包容量已经到j的状态，优化思路同01背包

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e2+10;
    int f[N],v[N][N],w[N][N],s[N];
    int n,m;
    int main() {
        cin>>n>>m;
        for (int i=1; i<=n; i++) {
            cin>>s[i];
            for (int j=0; j<s[i]; j++) {
                cin>>v[i][j]>>w[i][j];
            }
        }
        for (int i=1; i<=n; i++) {
            for (int j=m; j>=0; j--) {
                for (int k=0; k<s[i]; k++) {
                    if (j>=v[i][k]) {
                        f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
                    }
                }
            }
        }
        cout<<f[m];
        return 0;
    }

    数字三角形

    给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

f[i] [j] 表示从底向上走到第i行第j列累加的最大状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int f[N][N];
int n;
int main() {
    cin>>n;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=i; j++) {
            cin>>f[i][j];
        }
    }
    for (int i=n; i>=1; i--) {
        for (int j=1; j<=i; j++) {
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
        }
    }
    cout<<f[1][1];
    return 0;
}

最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

  • 朴素版O(n2)

    f[i] 代表以第i个数字结尾的序列的子序列最长长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int f[N],a[N];
int n;
int main() {
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>a[i];
    }
    int ans=0;
    for (int i=1; i<=n; i++) {
        f[i]=1;
        for (int j=1; j<=i; j++) {
            if (a[i]>a[j]) {
                f[i]=max(f[j]+1,f[i]);
            }
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

  • 贪心二分优化版O(nlogn)

    即维护一个数组f[N], 下标代表序列长度，值代表该长度的所有序列末尾的最小值，以确保后面加入新的数字，能使我们维护的序列尽可能地长。二分的时候找到不小于要加入的值的最小值并替换，如果找不到，直接在末尾加，增长序列长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    int f[N],cnt;
    int n;
    int main() {
        cin>>n;
        f[0]=-2e9;
        while (n--) {
            int x;
            cin>>x;
            if (x>f[cnt]) {
                f[++cnt]=x;
            }
            else{
                int l=1,r=cnt;
                while (l<r) {
                    int mid=l+r>>1;
                    if (f[mid]<x) {
                        l=mid+1;
                    }
                    else r=mid;
                }
                f[r]=x;
            }
        }
        cout<<cnt;
        return 0;
    }

    最长公共子序列

    给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

    f[i] [j]表示字符串A中前i位到字符串B中前j位所有共同子序列的集合，值维护的是其中的最大值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e3+10;
    int n,m,f[N][N];
    int main() {
        cin>>n>>m;
        char a[N],b[N];
        cin>>a+1>>b+1;
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                f[i][j]=max(f[i-1][j],f[i][j-1]);
                if (a[i]==b[j]) {
                    f[i][j]=max(f[i][j],f[i-1][j-1]+1);
                }
            }
        }
        cout<<f[n][m];
        return 0;
    }

    最短编辑距离

    给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

    1. 删除–将字符串 A 中的某个字符删除。
    2. 插入–在字符串 A 的某个位置插入某个字符。
    3. 替换–将字符串 A 中的某个字符替换为另一个字符。

    现在请你求出，将 A 变为 B 至少需要进行多少次操作。

    f[i] [j]表示字符串A中前i位的子串到字符串B所经过的最短操作

    为方便统计，每次操作都看为对A中的第i位字符进行操作

    • 对于操作一 要先将A中前i-1位变成B中的前j位，然后加上删除了A的第i的这个操作

      状态转移方程为f[i-1] [j]+1

    • 对于操作二 要先将A中前i位变成B中的前j-1位，然后再插入B中的第j位

      状态转移方程为f[i] [j-1]+1

    • 对于操作三 要先将A中前i-1位变成B中的前j-1位，然后再把A的第i位替换为B中的第j位，如果A的第i位和B中的第j位已经相等啦，则不用进行操作

      状态转移方程为f[i-1] [j-1]+1-int(a[i]==b[j])

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e3+10;
    int n,m,f[N][N];
    int main() {
        cin>>n;
        char a[N],b[N];
        cin>>a+1;
        cin>>m;
        cin>>b+1;
        for (int i=0; i<=m; i++) {
            f[0][i]=i;
        }
        for (int j=0; j<=n; j++) {
            f[j][0]=j;
        }
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
                f[i][j]=min(f[i][j],f[i-1][j-1]+1-int(a[i]==b[j]));
            }
        }
        cout<<f[n][m];
        return 0;
    }

    编辑距离

    最短编辑距离的应用

    给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

    对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

    每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e3+10;
    int n,m,f[N][N];
    char str[N][12];
    int editdist(char a[],char b[])
    {
        int la=(int)strlen(a+1),lb=(int)strlen(b+1);
        for (int i=0; i<=lb; i++) {
            f[0][i]=i;
        }
        for (int j=0; j<=la; j++) {
            f[j][0]=j;
        }
        for (int i=1; i<=la; i++) {
            for (int j=1; j<=lb; j++) {
                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
                f[i][j]=min(f[i][j],f[i-1][j-1]+1-int(a[i]==b[j]));
            }
        }
        return f[la][lb];
    }
    int main() {
        cin>>n>>m;
        for (int i=0; i<n; i++) {
            cin>>str[i]+1;
        }
        while (m--) {
            char t[12];
            cin>>t+1;
            int ans=0,cnt;
            cin>>cnt;
            for (int i=0; i<n; i++) {
                if (editdist(str[i], t)<=cnt) {
                    ans++;
                }
            }
            cout<<ans<<endl;
        }
      
        return 0;
    }

    石子合并

    设有 N 堆石子排成一排，其编号为 1，2，3，…，N。

    每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

    每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

    找出一种合理的方法，使总的代价最小，输出最小代价。

    f[i] [j]表示将i到j这一区间石子合并的最小代价

    先算出长度为1的区间然后算长度为2，3，…，N的

    对于每个要合并的区间，找到一个中间点，使合并的代价最小

    状态转移方程为f[i] [j]=min(f[i] [j],f[i] [k]+f[k+1] [j]+s[j]-s[i-1])

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e3+10,inf=1e9;
    int f[N][N],n;
    int s[N];
    int main() {
        cin>>n;
        for (int i=1; i<=n; i++) {
            cin>>s[i];
            s[i]+=s[i-1];
        }
        for (int len=2; len<=n; len++) {
            for (int i=1; i+len-1<=n; i++) {
                int j=i+len-1;
                f[i][j]=1e9;
                for (int k=i; k<=j; k++) {
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                }
            }
        }
        cout<<f[1][n];
        return 0;
    }

    整数划分

    一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。

    我们将这样的一种表示称为正整数 n 的一种划分。

    现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

    • 完全背包解法

      看成一个完全背包问题，即从1-n的数字中选出任意数量的任意数使它们加起来正好为n

      f[i] [j]代表用到前i个数，和为j的方案

      状态转移方程f[i] [j]=f[i-1] [j]+f[i] [j-i]

      一维优化后为f[j] += f[j-i] (容量由低到高枚举)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e3+10,mod=1e9+7;
    int f[N],n;
    int main() {
        cin>>n;
        f[0]=1;
        for (int i=1; i<=n; i++) {
            for (int j=i; j<=n; j++) {
                f[j]=(f[j]+f[j-i])%mod;
            }
        }
        cout<<f[n];
        return 0;
    }

    • 另一种很巧妙的解法

      将f[i] [j]定义为和为i用到了j个数的集合，其值就代表方案数

      对于每一个集合都可以划分为两个集合，一个为最小值为1，一个为最小值不为1

      对于最小值为1的集合，删掉一个1其一定可以和f[i-1] [j-1]的集合一一对应

      对于最小值不为1的集合，将每个数都减1其一定可以和f[i-j] [j]的集合一一对应

      所以状态转移方程为f[i] [j] = f[i - 1] [j-1] + f[i-j] [j]

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      #include <bits/stdc++.h>
      using namespace std;
      typedef long long ll;
      const int N=1e3+10,mod=1e9+7;
      int f[N][N],n;
      int main() {
          cin>>n;
          f[1][1]=1;
          for (int i=2; i<=n; i++) {
              for (int j=1; j<=i; j++) {
                  f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
              }
          }
          int ans=0;
          for (int i=1; i<=n; i++) {
              ans+=f[n][i];
              ans%=mod;
          }
          cout<<ans;
          return 0;
      }

计数问题

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。

分类讨论求1-n中某一数字出现的次数，然后利用前缀和的思想求出最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10,mod=1e9+7;
int get(int n)
{    
    int res=0;
    while (n) {
        res++;
        n/=10;
    }
    return res;
}
int count(int n,int k)
{
    int ans=0,cnt=get(n);
    for (int j=1; j<=cnt; j++) {
        int p=pow(10, cnt-j);
        int l=n/p/10,dj=n/p%10,r=n%p;
        ans+=(l-int(!k))*p;
        if (dj>k) {
            ans+=p;
        }
        if (dj==k) {
            ans+=r+1;
        }
    }
    return ans;
}
int main() {
    while (1) {
        int a,b;
        cin>>a>>b;
        if (!a) {
            break;
        }
        if (a>b) {
            swap(a,b);
        }
        for (int i=0; i<=9; i++) {
            cout<<count(b,i)-count(a-1,i)<<' ';
        }
        cout<<endl;
    }
    return 0;
}

蒙德里安的梦想（状态压缩DP）

求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。

例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。

f[i] [j]代表前i-1列已排好，此时第i列状态为j（有无突出的二进制状态转为十进制，0代表🈚️突出，1代表🈶️）的集合，其值为总方案数。所以f[m] [0]即为最终结果

状态转移方程为：f[i] [j]+= f[i-1] [k] 即加上前一列所有与当前状态不会发生冲突的方案

对可能发生的冲突进行预处理，然后进行dp方程的计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=12,M=1<<N;
ll f[N][M];
bool st[M];
vector<int> state[M];
int main() {
    int n,m;
    while (cin>>n>>m,n||m) {
        for (int i=0; i<1<<n; i++) {
            st[i]=true;
            int cnt=0;
            for (int j=0; j<n; j++) {
                if (i>>j&1) {
                    if (cnt&1) {
                        st[i]=false;
                        break;
                    }
                }
                else cnt++;
            }
            if (cnt&1) {
                st[i]=false;
            }
        }
        for (int j=0; j<1<<n; j++) {
            state[j].clear();
            for (int k=0; k<1<<n; k++) {
                if ((j&k)==0&&st[j|k]) {
                    state[j].push_back(k);
                }
            }
        }
        memset(f, 0, sizeof f);
        f[0][0]=1;
        for (int i=1; i<=m; i++) {
            for (int j=0; j<1<<n; j++) {
                for(auto k:state[j])
                    f[i][j]+=f[i-1][k];
            }
        }
        cout<<f[m][0]<<endl;
    }
    return 0;
}

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

i是已经走过的点二进制数转为十进制数

f[i] [j] 表示已经走过的点为i，且当前所在点为j的所有路径的集合，其值为最小值

状态转移方程为 f[i] [j]=min(f[i] [j],f[i-(1<<j)] [k]+w[k] [j])

只有当i中二进制表示第j为1且第k位也为1的时候才计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21,M=1<<N;
int w[N][N],f[M][N];
int main() {
    int n;
    cin>>n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin>>w[i][j];
        }
    }
    memset(f, 0x3f, sizeof f);
    f[1][0]=0;
    for (int i=0; i<1<<n; i++) {
        for (int j=0; j<n; j++) {
            if (i>>j&1) {
                for (int k=0; k<n; k++) {
                    if (i>>k&1) {
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1];
    return 0;
}

没有上司的舞会

树形dp➕深度优先搜索(dfs)

Ural 大学有 N 名职员，编号为 1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

f[u] [0]代表不选编号为u的这个人，以这个人为根结点的子树的最大值

f[u] [1]代表选编号为u的这个人，以这个人为根结点的子树的最大值

完成数据读入后，找出根结点，然后深度优先搜索根结点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int h[N],ne[N],e[N],idx;
int n,happy[N],f[N][2];
bool hasfa[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    f[u][1]=happy[u];
    for (int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=f[j][0];
    }
}
int main() {
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>happy[i];
    }
    memset(h, -1, sizeof h);//!!!别忘了初始化啊
    for (int i=1; i<n; i++) {
        int a,b;
        cin>>b>>a;
        hasfa[b]=true;
        add(a, b);
    }
    int root=1;
    while (hasfa[root]) {
        root++;
    }
    dfs(root);
    cout<<max(f[root][0],f[root][1]);
    return 0;
}

滑雪（记忆化搜索）

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

f[x] [y]代表以(x,y)为起点的最大滑行距离，每次滑行有四个方向能选择，所以遍历四个方向然后求最大值即可，利用记忆化搜索，即已经算过的点直接返回值来减少不必要的重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int h[N][N],f[N][N];
int n,m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int dp(int x,int y)
{
    int & v=f[x][y];
    if (v) {
        return v;
    }
    v=1;
    for (int i=0; i<4; i++) {
        int a=x+dx[i],b=y+dy[i];
        if (a>=1&&a<=n&&b>=1&&b<=m&&h[x][y]>h[a][b]) {
            v=max(v,dp(a, b)+1);
        }
    }
    return v;
}
int main() {
    cin>>n>>m;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin>>h[i][j];
        }
    }
    int ans=0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            ans=max(ans,dp(i, j));
        }
    }
    cout<<ans;
    return 0;
}