题目描述
和csp那个任务调度差不多
https://www.acwing.com/problem/content/description/3204/
动态规划
这类多个资源分配调度的问题有个共同点,就是把其中几个资源作为限制的维度,计算在这些限制下使用另一个资源的最小值。
令dp[u][i]为前u个任务A运行时长为i时,B运行的最短时间,并且第u个任务单独由A运行需要t1,单独由B运行需要t2,由AB同时运行需要t3
则:
dp[u][i] = min(dp[u-1][i-t1], dp[u-1][i]+t2, dp[u-1][i-t3]+t3)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, inf = 0x3f3f3f3f;
int tasks[6010][3];
int dp[2][30010]; //dp[i]: A运行时长为i时, B运行的最短时间
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> tasks[i][0] >> tasks[i][1] >> tasks[i][2];
}
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
int lim = 0;
for(int u = 1; u <= n; u++) {
int t1 = tasks[u][0], t2 = tasks[u][1], t3 = tasks[u][2], v = u - 1 & 1;
t1 = (t1 == 0 ? inf : t1);
t2 = (t2 == 0 ? inf : t2);
t3 = (t3 == 0 ? inf : t3);
lim += (min(t1, t3) == inf ? 0 : min(t1, t3));
if(t1 != inf) lim = max(lim, t1);
if(t2 != inf) lim = max(lim, t2);
if(t3 != inf) lim = max(lim, t3);
for(int i = 0; i <= lim; i++) {
// 只由B生产
dp[u & 1][i] = (t2 == inf ? t2 : dp[v][i] + t2);
// 只由A生产
if(i >= t1) dp[u & 1][i] = min(dp[u & 1][i], dp[v][i - t1]);
// 由A,B同时生产
if(i >= t3) dp[u & 1][i] = min(dp[u & 1][i], dp[v][i - t3] + t3);
}
}
int ans = inf;
for(int i = 0; i <= lim; i++) {
// 答案是A,B时长的最大值的最小值
ans = min(ans, max(i, dp[n & 1][i]));
}
cout << ans << endl;
return 0;
}
为什么csp那一题不能优化掉某一维呢?
我感觉可以,但没写出来。。
2
6 0 5
0 2 0
应该是6吧
是的捏,代码已修改