c++ - 从 ZCO 2014 解决 SUPW

Question

在为即将到来的 ZCO 练习时，我遇到了 this问题，这里是它的摘录，

In ICO School, all students have to participate regularly in SUPW. There is a different SUPW activity each day, and each activity has its own duration. The SUPW schedule for the next term has been announced, including information about the number of minutes taken by each activity.

Nikhil has been designated SUPW coordinator. His task is to assign SUPW duties to students, including himself. The school's rules say that no student can go three days in a row without any SUPW duty.

Nikhil wants to find an assignment of SUPW duty for himself that minimizes the number of minutes he spends overall on SUPW.

考虑 DP 解决方案，我花了一天的时间将它添加到接下来的 3 天，并取了它们的最小值以获得第二天 Nikhil 应该执行任务的时间，但我在比较的事情上几乎搞砸了，这就是我努力了，

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int calcmintime(std::vector<std::vector<int> >matrix,int n,int j,std::vector<int>duty){
    int time1 = matrix[0][j];
    int time2 = matrix[1][j];
    int time3 = matrix[2][j];
    if(time1+time2+time3 == 0){
        return 0;
    }
    if(time1 < time2 && time1 < time3 ){
        j = j + 1;
        return (duty[j]+calcmintime(matrix,n,j,duty));
    }
    if(time2 < time3 && time2 < time1 ){
        j = j + 2;
        return (duty[j]+calcmintime(matrix,n,j,duty));
    }
    if(time3 < time2 && time3 < time1 ){
        j = j + 3;
        return (duty[j]+calcmintime(matrix,n,j,duty));
    }
    if(time1 == time2 && time1 < time3){
        int a = j+1;
        int b = j+2;
        int forA = duty[j]+calcmintime(matrix,n,a,duty);
        int forB = duty[j]+calcmintime(matrix,n,b,duty);
        if(forA > forB){
            return forB;
        }else{
            return forA;
        }
    }
    if(time1 == time3 && time1 < time2){
        int a = j+1;
        int b = j+3;
        int forA = duty[j]+calcmintime(matrix,n,a,duty);
        int forB = duty[j]+calcmintime(matrix,n,b,duty);
        if(forA > forB){
            return forB;
        }else{
            return forA;
        }
    }
    if(time2 == time3 && time2 < time1){
        int a = j+3;
        int b = j+2;
        int forA = duty[j]+calcmintime(matrix,n,a,duty);
        int forB = duty[j]+calcmintime(matrix,n,b,duty);
        if(forA > forB){
            return forB;
        }else{
            return forA;
        }
    }
    if(time1 == time2 && time2 == time3){
        int a = j+1;
        int b = j+2;
        int c = j+3;
        int forA = duty[j]+calcmintime(matrix,n,a,duty);
        int forB = duty[j]+calcmintime(matrix,n,b,duty);
        int forC = duty[j]+calcmintime(matrix,n,c,duty);
        int result = forA;
        if(forB < result){
            result = forB;
        }
        if(forC < result){
            result = forC;
        }
        return result;
    }
}

int main(){
    int days;
    std::cin >> days;
    std::vector<int>dutyTime(days);
    //std::cout << "got it" << std::endl;
    for(int i=0;i<days;i++){
        std::cin >> dutyTime[i];
    }
    std::vector<std::vector<int> >timeMat(3,std::vector<int>(days,0));
    for(int i=0;i<3;i++){
        int j;
        for(j=0;j<days-1-i;j++){
            timeMat[i][j] = dutyTime[j] + dutyTime[j+1+i];
            //std::cout << timeMat[i][j] << ' ' << i << ' ' << j << ' ' << std::endl;
        }
        //std::cout << std::endl;
    }
    int mintime = INT_MAX;
    for(int i=0;i<3;i++){
        int newmin = dutyTime[i]+calcmintime(timeMat,days,i,dutyTime);
        if(newmin < mintime){
            mintime = newmin;
        }
    }
    std::cout << mintime << std::endl;
    return 0;
}

好的，这段代码给出了 12 次中的 2 次正确答案，所以我的方法是正确的，但应该错过了一些可能会扰乱我的程序的情况。谁能针对这个问题提出更好的方法？

更新:我尝试了另一种方法(尽管输入小于 4 时会有问题)，但结果是一样的:

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
    int n;
    std::cin >> n;
    std::vector<int>dutyTime(n);
    for(int i=0;i<n;i++){
        std::cin >> dutyTime[i];
    }
    std::vector<int>bestTime(n);
    bestTime[0] = dutyTime[0] + std::min(dutyTime[1],std::min(dutyTime[2],dutyTime[3]));
    bestTime[1] = dutyTime[1] + std::min(dutyTime[2],std::min(dutyTime[3],dutyTime[4]));
    bestTime[2] = dutyTime[2] + std::min(dutyTime[3],std::min(dutyTime[4],dutyTime[5]));
    for(int i=3;i<n-3;i++){
        bestTime[i] = std::min(bestTime[i-3],std::min(bestTime[i-2],bestTime[i-1])) + std::min(dutyTime[i+1],std::min(dutyTime[i+2],dutyTime[i+3]));
    }
    std::cout << bestTime[n-4] << std::endl;
    return 0;
}

注意:很抱歉，因为它是竞争性编程，我还没有记录下来

Answer 1

我很快就解决了它，代码也少了很多:)

代码如下:

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
    int n;
    std::cin >> n;
    std::vector<int>dutyTime(n);
    for(int i=0;i<n;i++){
        std::cin >> dutyTime[i];
    }
    std::vector<int>bestTime(n);
    bestTime[0] = dutyTime[0];
    bestTime[1] = dutyTime[1];
    bestTime[2] = dutyTime[2];
    for(int i=3;i<n;i++){
        bestTime[i] = dutyTime[i]+std::min(bestTime[i-1],std::min(bestTime[i-2],bestTime[i-3]));
    }

    std::cout << std::min(bestTime[n-1],std::min(bestTime[n-2],bestTime[n-3])) << std::endl;

    return 0;
}

解释:

对于前 3 天，最短可能时间只能是分配给当天本身的时间，对于接下来的几天，我们可以简单地选择最近三天的最短时间，然后加上分配给当天的时间，tada最后，最后三天的最短时间是 Nikhil 可以在营地度过的最短时间。