AcWing 4378. 选取数对

y总分析：这种题（我也不知道说的是哪种题hh）一般解法为贪心或dp，而本题用的是dp。

其实个人感觉题目不是很严谨，从y总讲解和题解分析得知各个数对区间是不能重叠的，但是题目使用的是≤，感觉数对的区间边界点是可以重复的。

方法1：y总的讲解，个人感觉比较难理解，也没有完全理解，因此只贴一个链接：第一届ACC(AcWing Cup)全国高校联赛_哔哩哔哩_bilibili

方法二：AcWing 4378. 选取数对(闫式dp分析法,但是要比y总讲的简单) - AcWing

思路：

闫式dp分析法

状态表示f[i][j]:表示在前i个数中选，j个区间的所有集合,属性:max

状态计算f[i][j]:根据最后一个区间是否包含最后一个点i来进行集合划分

1.不包含:f[i][j]=max(f[i][j],f[i-1][j])

2.包含:f[i][j]=max(f[i][j],f[i-m][j-1]+sum[i]-sum[i-m]) //如果包含i的话最后一个区间的右端点就是i

Java代码实现：

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

/**

 *

 */

public class Main {

    static int N=5000+5;

    //下标从1开始

    //f[i][j]的意思是从前i个数中选择k个数对

    static long[][] f=new long[N][N];

    static long[] sum=new long[N];

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] line = reader.readLine().split(" ");

        int n=Integer.parseInt(line[0]);

        int m=Integer.parseInt(line[1]);

        int k=Integer.parseInt(line[2]);

        line=reader.readLine().split(" ");

        //录入数据并计算前缀和

        for (int i = 0; i < n; i++) {

            sum[i+1]=Long.parseLong (line[i]);

            sum[i+1]+=sum[i];

        }

        for (int i = 1 ; i <= n; i++) {

            for (int j = 1; j <= k; j++) {

                //不选择第i个数

                f[i][j]=f[i-1][j];

                //如果选择第i个数作为末尾

                //不选择第i个数是无条件的，但是选择第i个数作为末尾必须保证：此数对可以选择，即此数对第一个数下标必须≥1

                if (i-m+1>=1) {

                    f[i][j]=Math.max(f[i][j], f[i-m][j]+sum[i]-sum[i-m]);

                }

            }

        }

        System.out.println(f[n][k]);

    }

}

方法三：https://www.acwing.com/solution/content/72485/

思路

和方法二本质上是相同的，只是进行了预处理，直接将原数组转换成了最终的一个一个数对的和值数组，然后也是最后一个数块的选择与否来进行集合的划分。

c++代码实现：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=5010;

ll n,m,k;

ll a[N],b[N];

ll w[N];

ll f[N][N];

int main()

{

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)

    {

        cin>>a[i];

        b[i]=b[i-1]+a[i];

    }

    ll cnt=0;

    for(int i=1;i+m-1<=n;i++)

    {

        //先将每个数对的之间的和单独做成一个数组，w即为此数组

        w[++cnt]=b[i+m-1]-b[i-1];//预处理区间

    }

    for(int i=1;i<=cnt;i++)

    {

        for(int j=1;j<=k;j++)

        {

            //i-m<0 因为数块下标从0开始，表示此数块如果选择的了的话就不能选择其他块了（取w[i]）

            //f[i][j]=max(不选此块,选此块);

            if(i-m<0) f[i][j]=max(f[i-1][j],w[i]);//此时最多选择一个区间

            //如果此数块可以选择，那么就在选择该块和不选之间取最大值。

            //即f[i][j]=max(不选此块,选此块);

            else f[i][j]=max(f[i-1][j],f[i-m][j-1]+w[i]);

        }

    }

    cout<<f[cnt][k];

    return 0;

}

巴特西