小美是团队的负责人,需要为团队制定工作的计划,以帮助团队产出最大的价值。
每周团队都会有两项候选的任务,其中一项为简单任务,一项为复杂任务,两项任务都能在一周内完成。第i周,团队完成简单任务的价值为li,完成复杂任务的价值为hi。由于复杂任务本身的技术难度较高,团队如果在第i周选择执行复杂任务的话,需要在i-1周不做任何任务专心准备。如果团队在第i周选择执行简单任务的话,不需要提前做任何准备。
现在小美的团队收到了未来N周的候选任务列表,请帮助小美确定每周的工作安排使得团队的工作价值最大。
小美是团队的负责人,需要为团队制定工作的计划,以帮助团队产出最大的价值。
每周团队都会有两项候选的任务,其中一项为简单任务,一项为复杂任务,两项任务都能在一周内完成。第i周,团队完成简单任务的价值为li,完成复杂任务的价值为hi。由于复杂任务本身的技术难度较高,团队如果在第i周选择执行复杂任务的话,需要在i-1周不做任何任务专心准备。如果团队在第i周选择执行简单任务的话,不需要提前做任何准备。
现在小美的团队收到了未来N周的候选任务列表,请帮助小美确定每周的工作安排使得团队的工作价值最大。
第一行为N(0≤N≤1000)
接下来的N行表示第1到N周两项候选任务的价值,第i行的格式为:li hi,其中 0 < li < 10000, 0< hi < 10000。
输出一个数字,表示小美团队在未来N周能产出的最大价值。
4 10 5 1 50 10 5 10 1
70
n = int(input().strip()) ans = [] for i in range(n): l,h = list(map(int,input().split())) ans.append([l,h]) dp = [0]*(n+1) dp[1] = max(ans[0][0],ans[0][1]) for i in range(2,n+1): dp[i] = max(ans[i-1][0]+dp[i-1],ans[i-1][1]+dp[i-2]) print(dp[-1])
# 我的解法:17/20 组用例通过。。。 # 因为这题有个坑: 第1周既可以做简单任务也可以做复杂任务,而我之前的理解是第1周只能做简单任务,因为没有前一周的准备时间啊 # 但这题默认在第一周前已经可以做好充分准备 def run(ls,hs): n=len(ls)#n=len(hs) #dp[i]:未来第i周能够获得的最大工作价值,i=1,2,...,n dp=[0 for _ in range(n+1)] # dp[0]无意义 # (~~划掉~~)初始化:第0周没有准备时间,所以只能选择做简单任务 # 初始化:第1周可以选择直接做复杂任务,也可以做简单任务 dp[1]=max(ls[0],hs[0]) # 从第2周开始,按照正常逻辑计算。。。 for i in range(2,n+1): # 可以选择做简单任务:dp[i]=dp[i-1]+ls[i] # 也可以选择做复杂任务(需要提前一周准备,此时前一周啥也不做,):dp[i]=dp[i-2]+hs[i] dp[i]=max(dp[i-1]+ls[i-1], dp[i-2]+hs[i-1]) return dp[n] while True: try: n=int(input()) if n==0: print(0) continue ls,hs=[],[] for _ in range(n): cur_l,cur_h=map(int,input().split(' ')) ls.append(cur_l) hs.append(cur_h) if n==1: print(ls[0]) continue res=run(ls,hs) print(res) except: break
import sys # 获得周数 N = int(sys.stdin.readline().strip()) # 获得每周两项任务的价值 taskValue = [] for i in range(N): temp = sys.stdin.readline().strip().split() taskValue.append([int(x) for x in temp]) # dp[i]为第i周开始时,累积的最大价值 dp = [0]*(N + 1) if N == 1: # 只有一周的话直接选择价值大的 print(max(taskValue[0][0], taskValue[0][1])) else: dp[1] = max(taskValue[0][0], taskValue[0][1]) for i in range(2, N + 1): # 比较简单任务和复杂任务哪个价值大 dp[i] = max(dp[i - 1] + taskValue[i - 1][0], dp[i - 2] + taskValue[i - 1][1]) print(dp[N])
#include<iostream> #include<stdlib.h> #include<string> #include<vector> using namespace std; int main(){ int nt; cin>>nt; vector<int> ll; vector<int> hl; for(int i=0; i<nt; ++i){ int l,h; cin>>l>>h; //cout<<l<<" "<<h<<endl; ll.push_back(l); hl.push_back(h); } vector<int> dpl(nt,0);//做简单任务最大 vector<int> dph(nt,0);//做复杂任务最大 dpl[0] = ll[0]; dpl[1] = ll[1] + max(dpl[0],hl[0]); dph[0] = hl[0]; dph[1] = hl[1]; for(int i=2; i<nt; ++i){ dpl[i] = max(ll[i]+dph[i-1], ll[i]+dpl[i-1]); dph[i] = max(hl[i]+dph[i-2], hl[i]+dpl[i-2]); //cout<<"S "<<dph[i]<<" "<<dpl[i]<<endl; } cout<<max(dpl[dpl.size()-1], dph[dph.size()-1])<<endl; return 0; }
N = int(input())
low = []
high = []
Z = N
d = [0]*(N+1) while N:
a,b = map(int,input().split())
low.append(a)
high.append(b)
N = N - 1 if Z == 0: print('0') elif Z == 1: print(max(low[0],high[0])) elif Z == 2: print(max(low[1]+low[0],high[1])) else:
d[1] = max(low[0],high[0])
d[2] = max(low[0]+low[1],high[0]+low[1],high[1]) for i in range(3,Z+1):
d[i] = max(d[i-1]+low[i-1],d[i-2]+high[i-1]) print(d[i])
n = int(input()) dp = [0] for i in range(n): l,h = input().split() l,h = int(l), int(h) if i == 0: dp.append(max(l,h)) else: dp.append(max(dp[i]+l, dp[i-1]+h)) print(dp[-1])
N = int(input().strip(' ')) data = [] for _ in range(N): cur = [int(i) for i in input().strip(' ').split(' ')] data.append(cur) dp = [[0] * (N+1) for _ in range(2)] dp[0][1] = data[0][0] #这里考虑了开始能做难工作的情况 dp[1][1] = data[0][1] for i in range(2,N+1): dp[0][i] = data[i-1][0] + max(dp[0][i-1],dp[1][i-1]) dp[1][i] = data[i-1][1] + max(dp[0][i-2],dp[1][i-2]) print(max(dp[0][-1],dp[1][-1]))
经典动态规划问题,动态规划的关键在于写出递推式,详细思路如下,应该是这里面写得最详细的:
# 动态规划 # 递推式(转移方程) # 如果选择简单任务 dp[i] = dp[i-1] + val[i-1][0] # 如果选择复杂任务 dp[i] = dp[i-2] + val[i-1][1] # 哪一个能得到最高的价值就选择哪一个(贪心策略) 即 # dp[i] = max(dp[i-1] + val[i-1][0], dp[i-2], val[i-1][1]) # 贪心策略为什么能得到最优解 因为两周之内要么做一个复杂任务 要么做两个简单任务 没有其他选择 # 选择两周之内的最大价值即为子问题局部最优解 很明显累积局部最优解能够得到全局最优解 n = int(input()) val = [] for i in range(n): val.append(list(map(int, input().split()))) def max_word_value(val): dp = [0] * (n+1) dp[1] = max(val[0][0], val[0][1]) for i in range(2, n+1): dp[i] = max(dp[i-1]+val[i-1][0], dp[i-2]+val[i-1][1]) return dp[n] print(max_word_value(val))
n = int(input()) L, H = [], [] for i in range(n): l, h = map(int, input().split()) L.append(l) H.append(h) dp = [0] * n if n>=1: if L[0] >= H[0]: dp[0] = L[0] else: dp[0] = H[0] if n>=2: if L[1] >= H[1]: dp[1] = dp[0] + L[1] else: if H[1] > L[1] + L[0]: dp[1] = H[1] else: dp[1] = dp[0] + L[1] for i in range(2, n): dp[i] = max(dp[i - 1] + L[i], dp[i - 2] + H[i]) print(dp[n-1])
def maxValue(n,l,h): pre,cur = 0,0 for i in range(n): pre,cur = cur ,max(pre+h[i],cur+l[i]) print('pre,cur',pre,cur) return cur n = int(input()) a,b = [],[] for i in range(n): x,y = map(int,input().split()) a.append(x) b.append(y) print(maxValue(n,a,b))动态规划,case通过率100%
# 动态规划 import sys n = int(sys.stdin.readline()) lst = [] for _ in range(n): lst.append(list(map(int, sys.stdin.readline().strip().split(" ")))) dp = [0] * n for i in range(n): if i == 0: dp[0] = max(lst[0][0], lst[0][1]) elif i == 1: dp[1] = max(dp[i - 1] + lst[1][0], lst[1][1]) else: dp[i] = max(dp[i - 1] + lst[i][0], dp[i - 2] + lst[i][1]) print(dp[-1])
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] low = new int[n]; int[] high = new int[n]; for(int i = 0; i < n; i++){ low[i] = sc.nextInt(); high[i] = sc.nextInt(); } int ans = getMaxValue(low,high); System.out.println(ans); } public static int getMaxValue(int[] low, int[] high){ int n = low.length; if(n == 0) return 0; if(n == 1) return low[0]; // dp[i][0] 表示在第 i 周做简单任务的最大值, // dp[i][1] 表示第 i 周做复杂任务的最大值 // int[][] dp = new int[n + 1][2]; // dp[1][0] = low[0]; dp[1][1] = high[0]; // for(int i = 2; i <= n; i++){ // // 简单任务 // dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1]) + low[i - 1]; // // 复杂任务 // dp[i][1] = Math.max(dp[i - 2][0],dp[i - 2][1]) + high[i - 1]; // } // return Math.max(dp[n][0],dp[n][1]); // 本周做简单任务和复杂任务的最大值 int easyValue = low[0], hardValue = high[0]; // 上周做简单任务和复杂任务的最大值 int postEasy = 0, postHard = 0; for (int i = 1; i < n; i++) { int _easy = easyValue; int _hard = hardValue; easyValue = Math.max(easyValue,hardValue) + low[i]; hardValue = Math.max(postEasy,postHard) + high[i]; postEasy = _easy; postHard = _hard; } return Math.max(easyValue,hardValue); } }
跟跳台阶一样。
#include<iostream> using namespace std; const int N = 1001; int f[N]; int l[N], h[N]; int main() { int n; cin>>n; for(int i=1; i<=n; ++i) cin>>l[i]>>h[i]; f[1] = max(h[1], l[1]); for(int i=2; i<=n; ++i) { f[i] = f[i-1] + l[i]; f[i] = max(f[i], f[i-2] + h[i]); } cout<<f[n]; }
# 动态规划 def helper(l,h,n): dp = [0]*n dp[0] = max(l[0],h[0]) if n == 1: return dp[0] dp[1] = max(l[0]+l[1],h[1]) if n ==2: return dp[1] for i in range(2,n): dp[i] = max(dp[i-1]+l[i],dp[i-2]+h[i]) return dp[-1] while True: try: n = int(input()) l,h =[0]*n,[0]*n for i in range(n): l[i],h[i] = map(int,input().split()) print(helper(l,h,n)) except: break