题目描述

有若干个任务需要在一台机器上运行。

它们之间没有依赖关系，因此可以被按照任意顺序执行。

该机器有两个 CPU 和一个 GPU。

对于每个任务，你可以为它分配不同的硬件资源:

在单个 CPU 上运行。
在两个 CPU 上同时运行。
在单个 CPU 和 GPU 上同时运行。
在两个 CPU 和 GPU 上同时运行。
一个任务开始执行以后，将会独占它所用到的所有硬件资源，不得中断，直到执行结束为止。

第 i 个任务用单个 CPU，两个 CPU，单个 CPU 加 GPU，两个 CPU 加 GPU 运行所消耗的时间分别为 ai,bi,ci 和 di。

现在需要你计算出至少需要花多少时间可以把所有给定的任务完成。

样例

输入格式
输入的第一行只有一个正整数 n，是总共需要执行的任务个数。

接下来的 n 行每行有四个正整数 ai,bi,ci,di，以空格隔开。

输出格式
输出只有一个整数，即完成给定的所有任务所需的最少时间。

输入样例：
3
4 4 2 2
7 4 7 4
3 3 3 3
输出样例：
7

解题思路

首先将四个调度可以分为三种，可以看到每种调度都需要CPU，所以，可以将调度2、4合并，记为新的调度3，
且可以放在其它所有任务之后执行，不会影响整体时间（这种占据所有资源，所以直接将占用时间累加到总时间上即可），
而调度1：占用一个CPU,调度2：占用一个CPU和一个GPU,调度1和调度1，调度1和调度2均不会冲突，
调度总时间直接加上调度的最大时间即可，但是调度2和调度2会由于争夺GPU而冲突，
假设使用CPU1总时间为i，CPU2总时间为j，GPU总时间为k
调度的总时间的最小值依旧为max(i,j,k),两个CPU错峰使用GPU即可，不会对最少总时间有影响
尝试使用DP求解
f[u][i][j][k]表示前u个任务，CPU1使用总时间i，CPU2使用总时间j,GPU使用总时间k时，
调度3占用时间的最小值，状态转移可以通过任务u的调度选择来完成

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int f[2][N][N][N];
int c[N][3];
int n;

int main()
{
    cin >> n;
    int m = 0;
    for(int i=1; i<=n; i++)
    {
        int x,y,z,t;
        cin >> x >> y >> z >> t;
        c[i][0] = x , c[i][1] = z, c[i][2] = min(y,t);
        m += x;
    }
    m = (m+1)/2;  // m表示所有任务均只使用一个CPU的总时间，也就是所有任务要完成的最大时间，有两个CPU，所以可以除以2，由于C++除法特性，所以先+1
    memset(f,0x3f,sizeof f);
    f[0][0][0][0] = 0;
    for(int u= 1; u <= n; u++)
        for(int i=0; i <= m; i++)
            for(int j = 0; j <= m; j++)
                for(int k = 0; k <= m; k++)
                {
                    int &v = f[u & 1][i][j][k];
                    register int x = c[u][0],y = c[u][1], z = c[u][2], t = u-1 & 1;
                    v = f[t][i][j][k] + z;  //选择调度3
                    if(i >= x)  v = min(v, f[t][i-x][j][k]);  //任务u选择CPU1
                    if(j >= x)  v = min(v, f[t][i][j-x][k]);  //选择CPU2
                    if(i >= y && k >= y)  v = min(v, f[t][i-y][j][k-y]);  // 选CPU1和GPU
                    if(j >= y && k >= y)  v = min(v, f[t][i][j-y][k-y]);  // 选CPU2和GPU
                }
    int res = INF;
    for(int i = 0; i <= m ; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= m ; k++)
                res = min(res,f[n & 1][i][j][k] + max(i,max(j,k)));
    //总时间要算加上调度1，2时间：max(i,max(j,k))
    cout << res << endl;

    return 0;
}