贝壳 砍木 用动态规划竟然只AC9 求指导

N = int(input()) A, B, C = [], [], [] for i in range(N):     a, b, c = list(map(int, input().split()))     A.append(a)     B.append(b)     C.append(c) def minTime(A, B, C, N):     dp = [[float('inf'), float('inf')] for i in range(N+1)]     dp[0] = [float('inf'), 0]     for i in range(1, N+1):         dp[i][0] = min(dp[i-1][0], dp[i-1][1] + C[i-1]) + A[i-1]         dp[i][1] = min(dp[i-1][1], dp[i-1][0] + C[i-1]) + B[i-1]      return min(dp[N]) print(minTime(A,B,C,N))

同dp A 9%

ac100N=int(input())for i in range(N):    abc=[int(j) for j in input().split()]    a,b,c=abc[0],abc[1],abc[2]    if i==0:        dpa,dpb=a c,b    else:        tmp=dpa        dpa=min(dpa a,dpb a c)        dpb=min(dpb b,tmp b c)print(min(dpa,dpb))

AC100,唯一一道ac的，尴尬 import sys def InputFunc(): n = int(input()) A = [] for i in range(n): tmp = list(map(int, input().strip().split())) A.append(tmp) return n, A def main(): n, A = InputFunc() if n == 0: print(0) return 0 max_value = sys.maxsize dp = [[max_value]*2 for _ in range(n)] for i in range(n): if i == 0: dp[i][1] = A[i][1] dp[i][0] = A[i][0]+A[i][2] else: dp[i][0] = min(dp[i-1][0]+A[i][0], dp[i-1][1] + A[i][0] + A[i][2]) dp[i][1] = min(dp[i-1][1]+A[i][1], dp[i-1][0] + A[i][1] + A[i][2]) print (min(dp[n-1][0], dp[n-1][1])) if __name__ == "__main__": main()

我是这么写的，一开始我也是双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; }

我感觉这道题有问题

我思路一样，100%呀

strip吧

这样说吧，四个题AC0.81

同0.09

😂同样思路 同9% 怀疑人生

#!/usr/bin/env python # coding=utf-8 # Python使用的是3.4.3，缩进可以使用tab、4个空格或2个空格，但是只能任选其中一种，不能多种混用 n = int(input()) lines = [] for i in range(0, n):     line = list(map(int, input().split()))     # read_list = [int(i) for i in input().split()]     lines.append(line) ans = 0 if n != 0:     b = lines[0][1]     a = lines[0][0]+ lines[0][2]     for i in range(1, n):         num = lines[i]         a_buf = a         b_buf = b         a = min(a_buf + num[0], b_buf + num[2] + num[0])         b = min(b_buf + num[1], a_buf + num[2] + num[1])     ans = min(a, b) print(ans , "\n")