在为即将到来的zco i cam acrossthis问题练习时，这里有一段摘录，
在ICO学校，所有学生都必须定期参加SUPW。
每天都有不同的SUPW活动，每个活动都有自己的
自己的持续时间下学期的SUPW计划已经公布了，
包括每个人所用分钟数的信息
活动。
Nikhil被指定为SUPW协调员。他的任务是分配
对学生负责，包括他自己。学校的规定是
任何学生都不能连续三天不履行任何义务。
尼基尔想给自己找份工作
减少他在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;
}
注：抱歉，因为是竞争性节目，我还没有记录下来
最佳答案
我很快就解决了这个问题，而且代码更少：）
代码如下：
#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天的最短可能时间只能是当天分配的时间，接下来的几天我们可以简单地选择最后3天的最短时间，加上当天分配的时间，最后3天的最短时间是尼基尔在营地中可以度过的最短可能时间。