我是这么写的,一开始我也是双dp 只过百分之9 不知道别人怎么过100的,但是保存四个状态比较好理解。
#include <iostream>
#include <vector>
#include<string>
#include<algorithm>
#include <numeric>
#include <limits>
#include<stdlib.h>
using namespace std;
double min_time(int n, double * a, double *b, double *c)
{
if (n <= 0) return 0;
double tmp1, tmp2;
double dp1[101] = { 0 };//上次斧头 这次锯子
double dp2[101] = { 0 };//上次锯子 这次斧头
double dp3[101] = { 0 };//上次斧头 这次斧头
double dp4[101] = { 0 };//上次锯子 这次锯子
dp1[1] = a[0] + c[0];
dp2[1] = b[0];
dp3[1] = b[0];
dp4[1] = a[0] + c[0];
for (int i = 2; i <= n; ++i)
{
dp1[i] = min(dp2[i - 1], dp3[i - 1]) + a[i - 1] + c[i - 1];
dp2[i] = min(dp1[i - 1], dp4[i - 1]) + b[i - 1] + c[i - 1];
dp3[i] = min(dp2[i - 1], dp3[i - 1]) + b[i - 1];
dp4[i] = min(dp1[i - 1], dp4[i - 1]) + a[i - 1];
}
tmp1 = min(dp1[n], dp2[n]);
tmp2 = min(dp3[n], dp4[n]);
return min(tmp1, tmp2);
}
int main() {
int n;
double a[101], b[101], c[101];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i] >> b[i] >> c[i];
}
cout << min_time(n, a, b, c) << endl;
return 0;
}