题目：车辆调度
使用三维dp，dp[a][b][k] 表示A、B两地分别需要a、b辆车，有k辆车可供调度时的最优解。
状态转移方程：
dp[a][b][k] = max(dp[a][b][k-1],
dp[a-1][b][k-1]+profits[k][0],
dp[a][b-1][k-1]+profits[k][1])
dp[a-1][b][k-1]+profits[k][0],
dp[a][b-1][k-1]+profits[k][1])
自测样例：
5 2 2
4 2
3 3
5 4
5 3
1 5
欢迎交流！
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
int main(){
int n=5, a=2, b=2;
vector<pair<int, int>> nums(n);
nums[0] = {4,2}; nums[1] = {3,3}; nums[2] = {5,4}; nums[3] = {5,3}; nums[4]={1,5};
vector<vector<vector<int>>> dp(a+1, vector<vector<int>>(b+1, vector<int>(n+1, 0)));
// initialize
for(int k=1; k<=n; k++){
dp[1][0][k] = max(dp[1][0][k-1], nums[k-1].first);
dp[0][1][k] = max(dp[0][1][k-1], nums[k-1].second);
}
// programming
for(int k=1; k<=n; k++)
for(int i=1; i<=a; i++)
for(int j=1; j<=b; j++){
// if(k>=i+j){
dp[i][j][k] = dp[i][j][k-1];
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+nums[k-1].first);
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+nums[k-1].second);
// }
}
cout<<dp[a][b][n]<<endl;
}
全部评论
(1) 回帖