小团的车辆调度

#include<iostream>
#include<cstring>
using namespace std;


int main(  ) {
        
     int n,a,b;
     cin>>n>>a>>b;

     int tab[a+1][b+1];
     memset(tab,0,sizeof(tab));
     int fx,fy;
       for(int i=1;i<=n;i++){
            cin>>fx>>fy;
           for(int j=min(a, i);j>= 0;j--){//j>=Math.max(0, a - n + i)  a+b<n , 剩余的车要有单接 max(0, a - n + i)
               for(int k= min(b, i-j);k>= 0;k--){//max(0, a +b - n + i-j)
                   int r1=tab[j][k];
                   if(j>=1){
                       int r2=tab[j-1][k]+fx  ;
                       if(r2>r1)r1=r2;
                   }
                   if(k>=1){
                       int r3=tab[j][k-1]+fy  ;
                       if(r3>r1)r1=r3;
                   }
                   tab[j][k]=r1;
               }
           }
          
       }

       cout<<tab[a][b] ;
      
   
   
}

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int main(){
    scanf("%d%d%d",&n,&a,&b);
    int dp[a+1][b+1];
    memset(dp, 0, sizeof(dp));
    int x,y;
    for(int k=1;k<=n;k++){
       scanf("%d%d",&x,&y);
        for(int i=min(a,k);i>=0;i--){
            for(int j=min(b,k-i);j>=0;j--){
                //使用max()比较的话会超时
                if(j>0&&dp[i][j]<dp[i][j-1]+y) 
                    dp[i][j]=dp[i][j-1]+y;
                if(i>0&&dp[i][j]<dp[i-1][j]+x)
                    dp[i][j]=dp[i-1][j]+x;
            }
        }
    }
    printf("%d\n",dp[a][b]);
}

python 优化后还是被卡了时间。可以顺便看看 97. 交错字符串 - 力扣（LeetCode） ，这两道题很像。

n, a, b = list(map(int, input().split(" ")))
profit_a, profit_b = [0], [0]
for _ in range(n):
    x, y = list(map(int, input().split(" ")))
    profit_a.append(x), profit_b.append(y)
pre = [[0] * (b + 1) for _ in range(a + 1)]
cur = [[0] * (b + 1) for _ in range(a + 1)]
for i in range(1, n + 1):
    for j in range(a + 1):
        for k in range(b + 1):
            if j + k > i:
                break
            if j == 0 and k == 0:
                continue
            if k == 0:
                cur[j][k] = max(pre[j][k], pre[j - 1][k] + profit_a[i])
            elif j == 0:
                cur[j][k] = max(pre[j][k], pre[j][k - 1] + profit_b[i])
            else:
                p_a = pre[j - 1][k] + profit_a[i]
                p_b = pre[j][k - 1] + profit_b[i]
                cur[j][k] = max(pre[j][k], p_a, p_b)
    pre, cur = cur, pre
print(pre[a][b])

#include "bits/stdc++.h"
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, a, b; std::cin >> n >> a >> b;
    // 选a个first， b个second -> max profit
    // 前i辆车，j个first，k个second
    std::vector<std::vector<std::vector<int>>> dp(2, std::vector<std::vector<int>>(a + 1, std::vector<int>(b + 1)));

    for (int i = 1;i <= n; i++) {
        int now = i & 1, pre = now ^ 1;
        int x, y; std::cin >> x >> y;
        for(int j = min(i, a);j >= max(0, a - (n - i)); j--) {
            for(int k = min(b, i - j);k >= max(0, a + b - n + i - j); k--) {
                dp[now][j][k] = dp[pre][j][k];
                if(j) dp[now][j][k] = max(dp[now][j][k], dp[pre][j - 1][k] + x);
                if(k) dp[now][j][k] = max(dp[now][j][k], dp[pre][j][k - 1] + y);
            }
        }        
    }

    std::cout << dp[n & 1][a][b] << std::endl;
}