Preview(2021-2022年度第三届全国大学生算法设计与编程挑战赛（夏季赛）——正式赛——E)

Preview

Description

题目背景

等上了大学，一切就好起来了。xxx同学一直被家里人这么说，但是实际上，等他上了大学才发现，大学真的太卷了。高中是大家基本都为了高考而努力，但是大学出路有很多条，而且条条路都有很多人在卷，卷的天昏地暗。大学老师经典的一句话是，大学的考试周之前，像是泡脚，轻松而惬意，大学考试周的时候，就是把自己的泡脚水喝下去。而现在，xxx同学正在因为这个考试周忙的头皮发麻，毕竟，他也不想挂科。

题目描述

xxx同学一共要学习n节课，我们把n节课要预习准备的时间以ai来进行统计，对于每一节课，我们都知道，学分越高，在大学就代表着学时越长，然后就更加重要，但是，相同学分的学科不一定价值一样，所以我们定义一个bi，代表预习时间的性价比。假设第i门考试会在第i天到来，而xxx同学如果选择在第i天预习这门学科，那么他在(i-ai,i+ai)的时间段就不能预习其他学科，得到的价值为ai*bi，（为什么不是考完就结束预习？因为苦逼的ddl人逃不过各种考完以后相对应的学科要交的报告）。xxx同学已经忙着考试周抽不出身了，他想请你求求能获得的最大价值。

Input

一个整数n，代表有n门学科需要预习1 <= n <= 100000

第二行，连续n个整数，表示要预习的时间ai, 1 <= ai <= n

第三行，连续n个整数，表示性价比bi,1 <= bi <= 100000

Output

一个整数x表示最大的价值

Sample Input 1

5
1 3 2 3 5
2 2 2 5 2

Sample Output 1

17

1)二维数组设计动态规划：
    状态设计：dp[i][j](i>=j)表示复习后i门课程，从第j天开始的总价值；
        选择第i门课程：  dp[i][j]=dp[i+1][i+a[i]+1]+a[i]*b[i];
        不选择第i门课程：dp[i][j]=dp[i+1][j];
    状态方程：dp[i][j]=max(dp[i+1][j],dp[i+1][i+a[i]+1]+a[i]*b[i]) (i>=j);
    并且由于题目的设定，只能从后往前递推，因为选择了第i门课，那么第i天以后的a[i]天都不能
    复习其他科目；如果从前往前递推，那么我选择了第i门课，那么选择第j门课的时候，要多少天
    以后我们才能选择第j门课呢。因为此时的下标是j，而不是i，无法得到a[i]的数值。

    当然，进行二维设计的时候，空间复杂度O(n^2)，显然会爆空间，后面进行一维状态设计求解。

for(int i=n;i>=1;--i)
        for(int j=i+a[i];j>=i-a[i]&&j>=1;--j)
        {
            if(j>i)
                dp[i][j]=dp[i+1][j];
            else
                dp[i][j]=max(dp[i+1][j],dp[i+1][i+a[i]+1]+a[i]*b[i]);
        }

/**
    1)二维数组设计动态规划：
    状态设计：dp[i][j](i>=j)表示复习后i门课程，从第j天开始的总价值；
        选择第i门课程：  dp[i][j]=dp[i+1][i+a[i]+1]+a[i]*b[i];
        不选择第i门课程：dp[i][j]=dp[i+1][j];
    状态方程：dp[i][j]=max(dp[i+1][j],dp[i+1][i+a[i]+1]+a[i]*b[i]) (i>=j);
    并且由于题目的设定，只能从后往前递推，因为选择了第i门课，那么第i天以后的a[i]天都不能
    复习其他科目；如果从前往前递推，那么我选择了第i门课，那么选择第j门课的时候，要多少天
    以后我们才能选择第j门课呢。因为此时的下标是j，而不是i，无法得到a[i]的数值。
 
    当然，进行二维设计的时候，空间复杂度O(n^2)，显然会爆空间，后面进行一维状态设计求解。
*/
/**
#include 
#include 
using namespace std;
 
const int maxn=1e3+10;
int dp[maxn][maxn]={0};
int a[maxn],b[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    for(int i=n;i>=1;--i)
        for(int j=i+a[i];j>=i-a[i]&&j>=1;--j)
        {
            if(i
                dp[i][j]=dp[i+1][j];
            else
                dp[i][j]=max(dp[i+1][j],dp[i+1][i+a[i]+1]+a[i]*b[i]);
        }
 
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
                cout << dp[i][j] << ' ';
            cout << endl;
        }
    cout << dp[1][1] << endl;
    return 0;
}
*/

2)一维数组设计动态归划:去掉二维的第一维便可。

正确代码

 for(int i=n;i>=1;--i)   //正确代码
        for(int j=i-a[i];j<=i+a[i];++j)
        {
            if(j<0)
                continue;
            dp[j]=dp[j];
            if(j<=i)
                dp[j]=max(dp[j],dp[i+a[i]+1]+a[i]*b[i]);
                //dp[i][j]=max(dp[i+1][j],dp[i+1][[i+a[i]+1]+a[i]*b[i];
        }

  有点错误：

 

//    for(int i=n;i>=1;--i) //这个应该是有缺陷的
//        for(int j=i+a[i];j>=i-a[i]&&j>=1;--j)
//        {
//            dp[j]=dp[j];
//            if(j<=i)
//                dp[j]=max(dp[j],dp[i+a[i]+1]+a[i]*b[i]);
//                //dp[i][j]=max(dp[i+1][j],dp[i][[i+a[i]+1]+a[i]*b[i];
//        }

/**
    2)一维数组设计动态归划:
    状态设计：dp[i][j](i>=j)表示复习后i门课程，从第j天开始的总价值；
        选择第i门课程：  dp[i][j]=dp[i+1][j+a[i]+1]+a[i]*b[i];
        不选择第i门课程：dp[i][j]=dp[i+1][j];
    状态方程：dp[i][j]=max(dp[i+1][j],dp[i+1][i+a[i]+1]+a[i]*b[i]) (i>=j);
    dp[j]=max(dp[j],dp[i+a[i]+1]]+a[i]*b[i]) (i>=j);
    并且由于题目的设定，只能从后往前递推，因为选择了第i门课，那么第i天以后的a[i]天都不能
    复习其他科目；如果从前往前递推，那么我选择了第i门课，那么选择第j门课的时候，要多少天
    以后我们才能选择第j门课呢。因为此时的下标是j，而不是i，无法得到a[i]的数值。
    data :
    10
    3 5 6 9 5 4 3 8 7 6
    15 4 6 5 7 9 8 6 7 8
*/
 
 
#include 
#include 
using namespace std;
 
const int maxn=1e6+10;
int dp[2*maxn]={0};
int a[maxn],b[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
 
    for(int i=n;i>=1;--i)   //正确代码
        for(int j=i-a[i];j<=i+a[i];++j)
        {
            if(j<0)
                continue;
            dp[j]=dp[j];
            if(j<=i)
                dp[j]=max(dp[j],dp[i+a[i]+1]+a[i]*b[i]);
                //dp[i][j]=max(dp[i+1][j],dp[i+1][[i+a[i]+1]+a[i]*b[i];
        }
 
//    for(int i=n;i>=1;--i) //这个应该是有缺陷的
//        for(int j=i+a[i];j>=i-a[i]&&j>=1;--j)
//        {
//            dp[j]=dp[j];
//            if(j<=i)
//                dp[j]=max(dp[j],dp[i+a[i]+1]+a[i]*b[i]);
//                //dp[i][j]=max(dp[i+1][j],dp[i][[i+a[i]+1]+a[i]*b[i];
//        }
 
//    for(int i=1;i<=n;++i)
//            cout << dp[i] << ' ';
//    cout << endl;
    cout << dp[1] << endl;
    return 0;
}