Eclipse's Blog
0%

20250309拼多多笔试算法练习

发表于 分类于

做题地址：https://oj.niumacode.com/training/37/problems

20250309_1_传送门1

签到题：先选负的值，再反转，再加上正的值。
也就是求所有数的绝对值之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<cmath>
using namespace std;

const int N = 100010;
int a[N];

int main() {
	int n;
    cin >> n;
    int ans = 0;
    for(int i = 0; i < n; i ++ ) {
        cin >> a[i];
        ans += abs(a[i]);
    }
    cout << ans << endl;
    return 0;
}

20250309_2_传送门2

动态规划，依次使用传送门，任意时刻反转

  • 定义状态
    • dp[i][0][0]：用到第i个传送门，用了0次反转到0点的最大距离
    • dp[i][0][1]：用到第i个传送门，用了0次反转到0点的最小距离
    • dp[i][1][0]：用到第i个传送门，用了1次反转到0点的最大距离
    • dp[i][1][1]：用到第i个传送门，用了1次反转到0点的最小距离
  • 状态转移方程
    • dp[i][0][0] = dp[i - 1][0][0] + a[i];
    • dp[i][0][1] = dp[i - 1][0][1] + a[i];
    • dp[i][1][0] = max({dp[i - 1][1][0], dp[i - 1][1][1], -dp[i - 1][0][0], -dp[i - 1][0][1]}) + a[i]; 分为前i-1没用过反转，前i-1用了反转
    • dp[i][1][1] = min({dp[i - 1][1][0], dp[i - 1][1][1], -dp[i - 1][0][0], -dp[i - 1][0][1]}) + a[i];
  • 初始化：
    • dp[i][0][0] = dp[i - 1][0][0] + a[i];
    • dp[i][0][1] = dp[i - 1][0][1] + a[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
      25
      26
      27
      28
      29
      #include<iostream>
      #include<algorithm>
      using namespace std;

      const int N = 100010;
      long long dp[N][2][2];
      int a[N];

      int main() {
          int n;
          cin >> n;
          for(int i = 0; i < n; i ++ ) {
              cin >> a[i];
          }
          dp[0][0][0] = dp[0][0][1] = a[0];
          dp[0][1][0] = dp[0][1][1] = -a[0];
          long long ans = abs(a[0]);
          for(int i = 1; i < n; i ++ ) {
              // 不反转
              dp[i][0][0] = dp[i - 1][0][0] + a[i];
              dp[i][0][1] = dp[i - 1][0][1] + a[i];
              // 反转
              dp[i][1][0] = max({dp[i - 1][1][0], dp[i - 1][1][1], -dp[i - 1][0][0], -dp[i - 1][0][1]}) + a[i];
              dp[i][1][1] = min({dp[i - 1][1][0], dp[i - 1][1][1], -dp[i - 1][0][0], -dp[i - 1][0][1]}) + a[i];
              ans = max(ans, max({abs(dp[i][0][0]), abs(dp[i][0][1]), abs(dp[i][1][0]), abs(dp[i][1][1])}));
          }
          cout << ans << endl;
          return 0;
      }

20250311_3_爱读书

动态规划

  • 定义状态
    • dp[i][j]：读到第i页，用了j分钟学到的最大知识量
  • 状态转移方程：
    • 一分钟读一页：dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i]);
    • 一分钟读两页：dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + (a[i] + a[i - 1]) / 2.0);
      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
      #include<iostream>
      #include<algorithm>
      #include<cstring>

      using namespace std;

      const int N = 1010;
      int a[N];
      double dp[N][N];

      int main() {
          int n, m;
          cin >> n >> m;
          if(m * 2 < n) {
              cout << -1 << endl;
              return 0;
          }
          for(int i = 1; i <= n; i ++ ) {
      		cin >> a[i];
          }
      	memset(dp, -0x3f, sizeof dp);
      	dp[0][0] = 0;
          for(int i = 1; i <= n; i ++ ) {
              for(int j = 1; j <= m; j ++ ) {
                  // 用一分钟读第i页
                  dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i]);
                  // 用一分钟读两页
                  if(i >= 2) {
                      dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + (a[i] + a[i - 1]) / 2.0);
                  }
              }
          }
          double ans = dp[n][1];
          for(int i = 1; i <= m; i ++ ) {
              ans = max(ans, dp[n][i]);
          }
          printf("%.1f\n", ans);
      	return 0;
      }