广联达4.13提前批笔试（C++）

计算机基础考察的比较细致，着重考察了类的继承，构造函数和析构函数，拷贝构造函数等（代码选择题的代码很长，有点恶心），每题一分所以其实不用花太多心思在上面。

让人摸不着头脑的是有60分的行测，不知道它出现在研发岗的笔试题里的目的是为啥（可能是照顾到一些没有很好基础的土木的同学？）。这部分可以花点时间做一做，一道题1.5分还是很划算的。

代码题一道，个人感觉是困难。最后只剩下半小时做了，所以没有太大的思路。之后看了大佬的思路，又整理了一下，也不知道实际上对不对，只是做一个记录，提醒一下自己dp这部分得好好看了,仅供参考，欢迎大家讨论。

题干

• 只有一道编程题，叫明明吃果子
• 明明要吃n个果子，有两种分别为红果子和绿果子，每次选一个吃。（n≤2000)
• 给了四个数组 a(n), b(n), c(n), d(n)，对于第i轮吃果子，假设之前的i-1轮吃了r个红果和g个绿果，
• 如果这一轮吃的是红果，则饱食度+ a[i]*r+b[i]*g;
• 如果这一轮吃的是绿果，则饱食度+ c[i]*r+d[i]*g;
• 问最大饱食度为多少

输入：

3
1 1 5 5
6 1 5 1
3 2 2 2

解释：第一行为吃的果子数n，后面每一行表示a[i],b[i],c[i],d[i].

输出:

12

思路

• 此题可用二维dp来做
• 设dp[i][j]，i表示第i轮吃果子，j表示到第i轮吃到的红果子总数，两层循环
• 如果这一轮吃的红果，则上一轮共有i-1个果子，其中红果数为j-1，绿果数为(i-1)-(j-1) = i-j个，则 dp[i][j]=dp[i-1][j-1] + a[i]*(j-1)+b[i]*(i-j);
• 如果这一轮吃的绿果，则上一轮共有i-1个果子，其中红果数为j，绿果数为(i-1)-(j) = i-j-1个，则 dp[i][j]=dp[i-1][j] + c[i]*j+d[i]*(i-j-1);
• 然后取这两种可能所产生的最大值赋给dp[i][j]
• 这样对于第n个果子，对j循环读取，得到最大值
• 这样就可以将时间复杂度转为O(n2)
• 注意一些边界问题，比如j=0时，不能选择吃红果；j=i时，不能选择吃绿果不然此轮吃的果子数会超.

int main()
{
    int n; cin >> n;
    vector<int> a(n+1), b(n+1), c(n+1), d(n+1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        cin >> b[i];
        cin >> c[i];
        cin >> d[i];
    }
    vector<vector<int>> dp(n+1, vector<int>(n+1));

    //j=0时，不能选择吃红果 for (int i = 2; i <= n; ++i)
    {
        dp[i][0] = dp[i-1][0] + d[i] * (i - 1);
    }
    //j=i时，不能选择吃绿果不然此轮吃的果子数会超 for (int i = 2; i <= n; ++i)
    {
        dp[i][i] = dp[i-1][i - 1] + a[i] * (i - 1);
    }

    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j < i ; ++j)
        {
            //这盘吃红果，则上一盘红果个数为j-1,绿果数为i-j
            int red = dp[i-1][j - 1] + a[i] * (j-1) + b[i] * (i - j);

            //这盘吃绿果，则上一盘红果个数为j,绿果数为i-j-1
            int green = dp[i-1][j] + c[i] * j + d[i] * (i-1 - j);
          
            dp[i][j] = red > green ? red : green;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; ++i)
    {
        if (dp[n][i] > ans) ans = dp[n][i];
   
    }
    cout<<ans;
  return 0;
}