贝壳找房08-10 算法岗部分题目及解答

局部最优不是全局最优

#include <iostream> #include <vector> #include <string.h> #include <algorithm> #include <map> #include<set> #include <unordered_map> #include <unordered_set> #include <math.h> using namespace std; int main() {     int n;     while(cin>>n){         vector<int> a(n, 0);         vector<int> b(n, 0);         vector<int> c(n, 0);         vector<int> dpa(n,0);         vector<int> dpb(n,0);         for(int i=0; i<n; ++i){             cin>>a[i];             cin>>b[i];             cin>>c[i];         }         dpa[0]=c[0]+a[0];         dpb[0]=b[0];         for(int i=1; i<n; ++i){             dpa[i] = min(dpa[i-1]+a[i], dpb[i-1]+c[i]+a[i]);             dpb[i] = min(dpb[i-1]+b[i], dpa[i-1]+c[i]+b[i]);         }         int res = dpa[n-1]<dpb[n-1] ? dpa[n-1]:dpb[n-1];         cout<<res<<endl;     }     return 0; }

卧槽 一毛一样 9% 二阶动态规划做的

用贪心的结果是 18%

我也百分之9，感觉就是维特比算法，不知道错在哪里了

time = [[0] * 2 for _ in range(n)] time[0][0] = a[0] + c[0] time[0][1] = b[0] for i in range(1, n):     time[i][0] = min(time[i-1][0] + a[i], time[i-1][1] + a[i] + c[i])     time[i][1] = min(time[i-1][0] + b[i] + c[i], time[i-1][1] + b[i]) print (min(time[-1][0], time[-1][1])) 这个应该是AC的。。

这题直接输出139就有9%